Please turn on javascript in your browser to play chess.
Science Forum

Science Forum

  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
    Originally posted by Eladar
    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
    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.
    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
    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!
    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:30 / 2 edits
    Originally posted by Eladar
    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?"
    --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.
  10. Standard member DeepThought
    Losing the Thread
    05 Nov '14 04:41
    Originally posted by Eladar
    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.

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

    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.
    "...isn't that hard anyway as it's just multiplication by 22."
    --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.
  13. 05 Nov '14 21:05
    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?
    "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.
  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:12 / 1 edit
    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.
    Yeah, I can see where you'd have problems making the distinction between thinking and thinking about useless things.

    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.