Enigma 1494 - Powerful logic
New Scientist magazine, 17 May 2008.
By Bob Walker.

Joe found this problem in one of his old
maths books and gave it to Penny to solve.
But as there was no solution in the book,
Joe programmed his computer to find the
answer and check Penny's.  All Penny had to
do was find the last three digits of:

              3^123456

What are they?

Ciao,
Chappy.

Let's see how long it takes for the last three digits to repeat
themselves:

001  003
002  009
003  027
004  081
005  243 <--- last digit repeats with period 4
006  729
007  187
008  561
009  683
010  049
011  147
012  441
013  323
014  969
015  907
016  721
017  163
018  489
019  467
020  401
021  203 <--- last two digits repeat with period 20
022  609
023  827
024  481
025  443
026  329
027  987
028  961
029  883
030  649
031  947
032  841
033  523
[...]
041  403
061  603
081  803
101  003 <--- last three digits repeat with period 100

How convenient.  :-)

So, we're going to need the last three digits to 3^56.  Taking the three
from 41 and multiplying them by the three from 15, we get 521.  (We get
the same 521 if we square the number from 028).

I cheated a bit in that I used the Windows calculator to do the
calculating by three, so that I wouldn't make any dumb mistakes trying
to calculate the answers in my head.

--
Ted S.
fedya at hughes dot net
Now blogging at http://justacineast.blogspot.com

On Wed, 2 Jul 2008 23:55:38 -0400, Ted Schuerzinger

I didn't realize how quickly the last THREE digits would repeat
themselves, but I saw that the third digit from the end followed an
identifiable pattern for how it changed with period 20.

For example...

16 is 721
36 is 121
56 is 521

So I could guess that...

76 is 921

And then I could guess that 156, 256 and so on would also end in 521.

On Jul 2, 10:55 pm, Ted Schuerzinger <fe...@hughes.spam> wrote:

I cheated a lot and simply used Python.

521

Old is right. these problems need to be updated to use 12 to 15
digit exponents. Otherwise, they don't qualify as enigmas.

Chappy said:

We are asked for 3^123456 modulo 1000. I use % to indicate modulo.

I can't recall whether a^b % c is equivalent to (a%c)^(b%c)%c, which will
slow me down a bit, but I am at least certain that a^b%c is equivalent to
(a%c)^b%c, so I can use that. (No doubt there is a much, much quicker way,
but never mind that for now.)

Because x^y * x^z = x^(y+z), m^n = m^(n/2) * m^(n/2) = (m^(n/2))^2, so:

3^123456 = (3^61728)^2 = ((3^30864)^2)^2 = (((3^15432)^2)^2)^2 =
((((3^7716)^2)^2)^2)^2 = (((((3^3858)^2)^2)^2)^2)^2 =
((((((3^1929)^2)^2)^2)^2)^2)^2 = ((((((3*((3^964)^2))^2)^2)^2)^2)^2)^2
= ((((((3*(((3^482)^2)^2))^2)^2)^2)^2)^2)^2
= ((((((3*((((3^241)^2)^2)^2))^2)^2)^2)^2)^2)^2
= ((((((3*((((3*((3^120)^2))^2)^2)^2))^2)^2)^2)^2)^2)^2
= ((((((3*((((3*(((3^60)^2)^2))^2)^2)^2))^2)^2)^2)^2)^2)^2
= ((((((3*((((3*((((3^30)^2)^2)^2))^2)^2)^2))^2)^2)^2)^2)^2)^2
= ((((((3*((((3*(((((3^15)^2)^2)^2)^2))^2)^2)^2))^2)^2)^2)^2)^2)^2
= ((((((3*((((3*(((((3*((3^7)^2))^2)^2)^2)^2))^2)^2)^2))^2)^2)^2)^2)^2)^2

We calculate 3^7 directly: 3^3 is 27, 27^2 is 729, and 3*729 is 2187.

((((((3*((((3*(((((3*((3^7)^2))^2)^2)^2)^2))^2)^2)^2))^2)^2)^2)^2)^2)^2
= ((((((3*((((3*(((((3*(2187^2))^2)^2)^2)^2))^2)^2)^2))^2)^2)^2)^2)^2)^2

From now on, all = signs are assumed to mean "equals (modulo 1000)":

((((((3*((((3*(((((3*(2187^2))^2)^2)^2)^2))^2)^2)^2))^2)^2)^2)^2)^2)^2
= ((((((3*((((3*(((((3*(187^2))^2)^2)^2)^2))^2)^2)^2))^2)^2)^2)^2)^2)^2

187^2 is 34969, which is 969 (mod 1000).

((((((3*((((3*(((((3*(187^2))^2)^2)^2)^2))^2)^2)^2))^2)^2)^2)^2)^2)^2
= ((((((3*((((3*(((((3*969)^2)^2)^2)^2))^2)^2)^2))^2)^2)^2)^2)^2)^2
= ((((((3*((((3*(((((2907)^2)^2)^2)^2))^2)^2)^2))^2)^2)^2)^2)^2)^2
= ((((((3*((((3*((((907^2)^2)^2)^2))^2)^2)^2))^2)^2)^2)^2)^2)^2
= ((((((3*((((3*(((822649^2)^2)^2))^2)^2)^2))^2)^2)^2)^2)^2)^2
= ((((((3*((((3*(((649^2)^2)^2))^2)^2)^2))^2)^2)^2)^2)^2)^2
= ((((((3*((((3*((421201^2)^2))^2)^2)^2))^2)^2)^2)^2)^2)^2
= ((((((3*((((3*((201^2)^2))^2)^2)^2))^2)^2)^2)^2)^2)^2
= ((((((3*((((3*(40401^2))^2)^2)^2))^2)^2)^2)^2)^2)^2
= ((((((3*((((3*(401^2))^2)^2)^2))^2)^2)^2)^2)^2)^2
= ((((((3*((((3*160801)^2)^2)^2))^2)^2)^2)^2)^2)^2
= ((((((3*(((482403^2)^2)^2))^2)^2)^2)^2)^2)^2
= ((((((3*(((403^2)^2)^2))^2)^2)^2)^2)^2)^2
= ((((((3*((162409^2)^2))^2)^2)^2)^2)^2)^2
= ((((((3*((409^2)^2))^2)^2)^2)^2)^2)^2
= ((((((3*(167281^2))^2)^2)^2)^2)^2)^2
= ((((((3*(281^2))^2)^2)^2)^2)^2)^2
= ((((((3*78961)^2)^2)^2)^2)^2)^2
= (((((236883^2)^2)^2)^2)^2)^2
= (((((883^2)^2)^2)^2)^2)^2
= ((((779689^2)^2)^2)^2)^2
= ((((689^2)^2)^2)^2)^2
= (((474721^2)^2)^2)^2
= (((721^2)^2)^2)^2
= ((519841^2)^2)^2
= ((841^2)^2)^2
= (707281^2)^2
= (281^2)^2
= 78961^2
= 961^2
= 923521
= 521.

Since (a%c)^(b%c)%c gives the same result, I am somewhat reassured that
this would have been a valid short-cut, but of course one good example
doesn't make a general proof.

So - what's the quick way?

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999

In article <d91585c5-1aee-4f69-9625-26545affc...@r37g2000prm.googlegroups.com>,

My first thought was to use Euler-Fermat, which reduces the problem to
finding 3^256, since phi(1000) = 400.  And 3^256 can be found by
repeated squaring.  But here's a much simpler way.

3^123456 = 9^61728 = (10-1)^61728

Expanding, we can ignore all the powers of 10 greater than 2, leaving:

(61728-choose-2) * 10^2  -  61728*10 + 1

We could reach for a calculator to find 61728-choose-2, but as we're
going to reduce mod 1000 at the end, and we have that 10^2 already, it's
enough to worry about its final digits.  Similarly for the 61728*10.

So we get: 8*7/2 * 100 - 280 + 1 = 2521.

So the answer is 521.

Gareth

Even that piece of Python is inefficient. The quick way is

521

which works internally by doing a proper modular exponentiation,
reducing mod 1000 at every stage. Much more efficient than bothering
to calculate all those upper digits that weren't going to be needed
anyway.

That function is a viable way to do modular exponentiation with both
the exponent and modulus in the region of kilobits, still in seconds
(since that's what it mostly gets used for - RSA and Diffie-Hellman
and so on).

12-15 digit modexps? _Still_ peanuts.

Only if you permit answers without working to count as solutions. A
simple way to enforce that solvers find a way that doesn't involve
Python is to consider the question to have an implicit "Prove" at
the start. Then, any answer that begins "I fed it into a computer"
attracts an immediate "fine, so now mathematically prove your
computer is right".

Of course, you could still use Python to check that your by-hand
proof did yield the right answer, or to print out reams of numbers
which you can examine to find the patterns for which you then seek
mathematical justification. But really, if it's that easy to get the
answer with a computer, then just getting the answer isn't going to
impress anyone.
--
Simon Tatham         "What a caterpillar calls the end of the
<ana...@pobox.com>    world, a human calls a butterfly."

In article <2ll*4h...@news.chiark.greenend.org.uk>,
Gareth Taylor  <gtay...@chiark.greenend.org.uk> wrote:

I should have written a bit more here.  Because we're dividing by 2 in
the first term, we should worry about the next digit up as well.  After
all, 28*27 = 756, but 18*17 = 306.  The division by 2 would bring that
difference down to a digit we actually care about.

But, in this case we do have an even tens digit in 61728, so it is
enough to consider only the final digits.

Gareth

Richard Heathfield  <r...@see.sig.invalid> wrote:

As Gareth mentioned in passing in his answer, the theorem you're
looking for is the Euler-Fermat theorem (or Fermat-Euler theorem),
which states that if a and c are coprime then a^phi(a) is congruent
to 1 mod c, where phi is
  http://en.wikipedia.org/wiki/Euler's_totient_function
Hence, if you're trying to raise a to some arbitrary power b mod c,
you can't get away with reducing b itself mod c, but you can reduce
b mod phi(c).

For coprime a,b, phi(ab)=phi(a)phi(b); and for any prime power,
phi(p^a) = (p-1)p^(a-1). Hence, phi(1000) = phi(2^3)*phi(5^3) =
1*2^2*4*5^2 = 400 (as Gareth also mentioned). So if your eventual
result will be reduced mod 1000, you can reduce b mod 400. (And you
are of course correct in saying you can also reduce a mod 1000.)
--
Simon Tatham         "Imagine what the world would be like if
<ana...@pobox.com>    there were no hypothetical situations..."

In article <d91585c5-1aee-4f69-9625-26545affc...@r37g2000prm.googlegroups.com>,

521.  But I suppose the idea is to come up with an elegant way of
figuring it out without computing 3^123456.  I just used 'bc'.

However, were I to do it the "right way", first I'd note that 3^123456
= 9^61728.  I do this because there's often tricks with 9s.  Then I
note that the last digit of powers of 9 alternates between 1 and 9.
That gives me the 1 So then I note 9^61728 = 81^30864.  The next to
last digit of powers of 81 appears to follow a pattern 8,6,4,2,0.
That gives me the 2. Then I note that 81^30864 = 3486784401^6172 *
81^4.  The third to last digit of the powers of 3486784401 follow the
pattern 4,8,2,6,0, so 3486784401^6172 ends with 801.  801 * 81^4 ends
in 521, and thus so does 3^123456.  Messy but tractable even by hand.
Probably there's a better way to do it than that.
--
  There's no such thing as a free lunch, but certain accounting practices can
  result in a fully-depreciated one.

On 3 Jul, 09:40, Simon Tatham <ana...@pobox.com> wrote: