Recreational Mathematics Problem 2

Duchess64
Science 03 Nov '14 22:21
1. 03 Nov '14 22:21
Here's a problem from elementary number theory:

Let A and B be integers such that A > B > 0.
The last three digits are the same in the decimal representations of
1978^A and 1978^B. What is the minimum value C = A + B ?

Advice: One needs some basic knowledge of number theory, particularly of
modular arithmetic. Having that, this problem does not require any deep
insight, only determined manipulation with perhaps a touch of cleverness.

If someone's interested in this problem and lacks any knowledge of number
theory, then I would not object to one consulting Wikipedia, YouTube (if it
turns you on), or even a textbook (gasp!) to learn some basic concepts.
I lack the time to comment upon every detail of everyone's attempted
solution, yet I shall confirm a correct solution or post one myself after a
fair amount of time has elapsed.

Good luck to everyone who's willing to make an honest effort.
2. 04 Nov '14 18:13
Are calculators allowed?
3. 04 Nov '14 20:14
Are calculators allowed?
No, I usually ask everyone to rely upon one's brain and enjoy the challenge.
There would be no challenge if you could look up the problem and its solution
on the internet (I don't know if it's there). And there would be little challenge
if you could use a 'brute-force' resource like a calculator or a computer.
I expect that one could write a computer program to solve this problem.
In this case, given that some people may be completely ignorant of modular
arithmetic, I don't object to them consulting a textbook on number theory.

Originally, a problem like this might have been given in a real-timed
problem-solving competition to students who were expected to use only
their brains and pencil and paper.
4. 04 Nov '14 21:19
Originally posted by Duchess64
No, I usually ask everyone to rely upon one's brain and enjoy the challenge.
There would be no challenge if you could look up the problem and its solution
on the internet (I don't know if it's there). And there would be little challenge
if you could use a 'brute-force' resource like a calculator or a computer.
I expect that one could write a computer ...[text shortened]... lving competition to students who were expected to use only
their brains and pencil and paper.
If you really want to rely on your brain, then no scratch work allowed.

If you write stuff down, then you are also relying on your fingers, paper and pen/pencil.
5. 04 Nov '14 21:29
If you really want to rely on your brain, then no scratch work allowed.
If you write stuff down, then you are also relying on your fingers, paper and pen/pencil.
Eladar's trolling again. Obviously, writing down on paper how one solved
the problem is *required* in a competition for a student to receive credit.
Little or no credit would be given for a student's extremely lucky guess.
6. 05 Nov '14 01:30
Originally posted by Duchess64
Eladar's trolling again. Obviously, writing down on paper how one solved
the problem is *required* in a competition for a student to receive credit.
Little or no credit would be given for a student's extremely lucky guess.
I didn't know this was a 'credit' assignment. I thought you were arguing that using a pencil and paper to do calculations was a greater mental challenge than simply using a calculator.

I then suggested that having to visualize the problem and remember the answers would be an even greater mental challenge and therefore more fun!
7. 05 Nov '14 01:42
I didn't know this was a 'credit' assignment. I thought you were arguing that using a pencil and paper to do calculations was a greater mental challenge than simply using a calculator.

I then suggested that having to visualize the problem and remember the answers would be an even greater mental challenge and therefore more fun!
If Eladar's finished trolling (which I doubt), why doesn't he (apart from
his evident lack of intelligence) attempt to solve this problem?
8. 05 Nov '14 01:46
Originally posted by Duchess64
If Eladar's finished trolling (which I doubt), why doesn't he (apart from
his evident lack of intelligence) attempt to solve this problem?
Why do I not solve the problem?

I do not find multiplication by hand to be an entertaining endeavor.
9. 05 Nov '14 02:302 edits
Why do I not solve the problem?
I do not find multiplication by hand to be an entertaining endeavor.
"Why do I not solve this problem?"

Evidently, Eladar's much much too stupid to solve this problem.
Hint: Solving the problem requires hardly any 'multiplication by hand'.
(I could do all required multiplication in my head.)

I am sounding unpleasant toward Eladar *only* because he's obviously a
persistent troll who's *not* making any honest effort to solve this problem.
10. DeepThought
05 Nov '14 04:41
Why do I not solve the problem?

I do not find multiplication by hand to be an entertaining endeavor.
Lot's of multiplication isn't needed, and isn't that hard anyway as it's just multiplication by 22.

(1978^A)%1000 = (1978%1000 * (1978^A-1))%1000 = (978 * (1978^(A-1))%1000,

as (ab)%c = (a(b%c))%c, iterating this we get:

(1978^A)%1000 = (978^A)%1000.

For N some integer:

(N*978)%1000 = (N*(1000 - 22))%1000 = (1000*N - 22*N)%1000 = 1000 - (22*N)%1000

so we never need to multiply by anything bigger than 22.

If (978^A)%1000 = (978^B)%1000, then (22^A)%1000 = (22^B)%1000 which means we only need to look at powers of 22.

(22^A)%1000 = (((2^A)%1000) * (11^A)%1000)%1000

This is a method for generating random numbers on a computer. The sequence repeats after at least 400 steps as 11^A has least significant digit 1 and 2^A has least significant digit one of {2, 4, 6, 8}, so there are only 4 possibilities for the least significant digit which gives B = 1, A = 401 and C = 402 at most. I need to think about it to get any further.
11. 05 Nov '14 19:503 edits
Originally posted by Duchess64
"Why do I not solve this problem?"

Evidently, Eladar's much much too stupid to solve this problem.
Hint: Solving the problem requires hardly any 'multiplication by hand'.
(I could do all required multiplication in my head.)

I am sounding unpleasant toward Eladar *only* because he's obviously a
persistent troll who's *not* making any honest effort to solve this problem.
Yes, I'm much too stupid to know how to multiply.

Gotcha.

And much like any puzzle, once you know the proper approach the result is much easier. I'm too normal to enjoy thinking about useless problems for long periods of time. If being normal makes be dumb, so be it.

Btw, Isn't there an entire forum on this site devoted to puzzles?
12. 05 Nov '14 20:581 edit
Originally posted by DeepThought to Eladar
Lot's of multiplication isn't needed, and isn't that hard anyway as it's just multiplication by 22.

(1978^A)%1000 = (1978%1000 * (1978^A-1))%1000 = (978 * (1978^(A-1))%1000,

as (ab)%c = (a(b%c))%c, iterating this we get:

(1 ...[text shortened]... it which gives B = 1, A = 401 and C = 402 at most. I need to think about it to get any further.
"...isn't that hard anyway as it's just multiplication by 22."

I doubt that Eladar comprehends 1978 = -22 (mod 1000) or cares to learn.

Eladar's preferred 'contribution' to this forum was to argue that black people
are 'racially inferior' in mathematical ability, if not also general intelligence,
to white people. Eladar discontinued his argument only because I could cite
the same 'scientific tests' to show white people are inferior to East Asians.
13. 05 Nov '14 21:05
Yes, I'm much too stupid to know how to multiply.

Gotcha.

And much like any puzzle, once you know the proper approach the result is much easier. I'm too normal to enjoy thinking about useless problems for long periods of time. If being normal makes be dumb, so be it.

Btw, Isn't there an entire forum on this site devoted to puzzles?
"I'm too normal to enjoy thinking ..."

It's already been widely noticed in more than one forum.

"If being normal makes me dumb, so be it."

There's some correlation between low intelligence and racial prejudice.
14. 06 Nov '14 00:11
Originally posted by DeepThought

(1978^A)%1000 = (978^A)%1000.

It doesn't take high levels of math to understand that the last three digits of a multiplication problem has nothing to do with place values greater than the hundreds place.
15. 06 Nov '14 00:121 edit
Originally posted by Duchess64
"I'm too normal to enjoy thinking ..."