Re: Enigma 1494 - Powerful logic
- From: johnjo <a1jrj@xxxxxxxxxxx>
- Date: Fri, 4 Jul 2008 06:27:48 -0700 (PDT)
On 3 Jul, 09:40, Simon Tatham <ana...@xxxxxxxxx> wrote:
Richard Heathfield <r...@xxxxxxxxxxxxxxx> 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...@xxxxxxxxx> there were no hypothetical situations..."
I think the rationale for this puzzle was to expose those who like
numbers to the
howler: mod(a^b, n) = mod(a ^ (mod(b,n)), n) -- which it isnt
since no-one followed up with the calculation, let me.
123456 = 256 mod 400
and 256 is 2^8 and this is significant, since to calculate exponents
to a modulus you need to square and multiply in a russian style
but here all we need to do is square 3, 8 times, each mod 1000.
after 81 the "1" is invariant, and if you have at one stage three
digits
(a, b, 1) then the next stage gives (b^2 + 2a, 2b, 1) (with carry as
required)
so the second digit is a power of 2 mod 10 and we can write down 21
for the 8th stage right away
the third digit just needs to be calculated - cant see an easy way and
yes it is 5.
interestingly the first solution noted that 3^100 = 3 mod 1000 so the
answer is also 3^56
this looks easier to do, but 56 = 111000 binary and so we need to
SMSMSSS (S = square, M=multiply by 3) which is 7 operations rather
than 8, so it isnt that much easier.
HTH
JJ
.
- References:
- Enigma 1494 - Powerful logic
- From: Chappy
- Re: Enigma 1494 - Powerful logic
- From: Richard Heathfield
- Re: Enigma 1494 - Powerful logic
- From: Simon Tatham
- Enigma 1494 - Powerful logic
- Prev by Date: puzzle source
- Next by Date: Re: multiply
- Previous by thread: Re: Enigma 1494 - Powerful logic
- Next by thread: Re: Enigma 1494 - Powerful logic
- Index(es):
Relevant Pages
|
