- 03 Nov '14 22:21Here'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. - 04 Nov '14 20:14

No, I usually ask everyone to rely upon one's brain and enjoy the challenge.*Originally posted by Eladar***Are calculators allowed?**

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. - 04 Nov '14 21:19

If you really want to rely on your brain, then no scratch work allowed.*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 write stuff down, then you are also relying on your fingers, paper and pen/pencil. - 04 Nov '14 21:29

Eladar's trolling again. Obviously, writing down on paper how one solved*Originally posted by Eladar***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.

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. - 05 Nov '14 01:30

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.*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 then suggested that having to visualize the problem and remember the answers would be an even greater mental challenge and therefore more fun! - 05 Nov '14 01:42

If Eladar's finished trolling (which I doubt), why doesn't he (apart from*Originally posted by Eladar***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!

his evident lack of intelligence) attempt to solve this problem? - 05 Nov '14 02:30 / 2 edits

"Why do I not solve this problem?"*Originally posted by Eladar***Why do I not solve the problem?**

I do not find multiplication by hand to be an entertaining endeavor.

--Eladar

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. - 05 Nov '14 04:41

Lot's of multiplication isn't needed, and isn't that hard anyway as it's just multiplication by 22.*Originally posted by Eladar***Why do I not solve the problem?**

I do not find multiplication by hand to be an entertaining endeavor.

I've got some ideas about this which I'll post since no one seems to have made any progress. First note that:

(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. - 05 Nov '14 19:50 / 3 edits

Yes, I'm much too stupid to know how to multiply.*Originally posted by Duchess64***"Why do I not solve this problem?"**

--Eladar

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.

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? - 05 Nov '14 20:58 / 1 edit

"...isn't that hard anyway as it's just multiplication by 22."*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.**

I've got some ideas about this which I'll post since no one seems to have made any progress. First note that:

(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.

--DeepThought (to Eladar)

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. - 05 Nov '14 21:05

"I'm too normal to enjoy thinking ..."*Originally posted by Eladar***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?

--Eladar

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

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

--Eladar

There's some correlation between low intelligence and racial prejudice. - 06 Nov '14 00:12 / 1 edit

Yeah, I can see where you'd have problems making the distinction between thinking and thinking about useless things.*Originally posted by Duchess64***"I'm too normal to enjoy thinking ..."**

--Eladar

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

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

--Eladar

There's some correlation between low intelligence and racial prejudice.

Btw, the belief that race has no effect on intelligence is just as racists as the opposite belief. Any assumption based on race is by definition racist.

In other words, everyone is a racist. You simply believe your form of racism doesn't stink.