Re: Counterexample to t( (c^n - a^n) mod b ) | phi(b)
From: Doug Goncz (dgoncz_at_aol.com)
Date: 11/19/04
- Next message: Phil Carmody: "Re: astonishingly many numbers with abundace 12 and 56"
- Previous message: Han de Bruijn: "Re: Infinite square roots problem - I can't solve it!"
- In reply to: Daniel W. Johnson: "Re: Counterexample to t( (c^n - a^n) mod b ) | phi(b)"
- Next in thread: Daniel W. Johnson: "Re: Counterexample to t( (c^n - a^n) mod b ) | phi(b)"
- Reply: Daniel W. Johnson: "Re: Counterexample to t( (c^n - a^n) mod b ) | phi(b)"
- Messages sorted by: [ date ] [ thread ]
Date: 19 Nov 2004 12:29:12 GMT
Dear Daniel,
You wrote
>From: panoptes@iquest.net (Daniel W. Johnson)
>c^(n+phi(b)) - c^n is a multiple of b (for sufficiently large n in the
>case that gcd(b,c) > 1).
This seems to be a misapplication of Euler's totient theorem, that for
relatively prime a and n
a^(phi(n)) == 1 mod n
Is it?
We don't need to consider the case gcd(b,c)>1. gcd(a,b,c)=1 is given in the OP
to this thread.
Given b | c^(n+phi(b))-c^n, what you say would be true. Whence cometh this
assertion? It's as if you are implying
c^(n+phi(b)) - c^n = c^(phi(b))
and we know this can't be true because while subtraction is associative under
multiplication, it is not associative under exponentiation.
The counter example a,b,c = 5,6,7 shows that the period of
c^n - a^n (mod b)
does not necessarily divide phi(b).
>The same is true of a^(n+phi(b)) - a^n.
>
>Therefore (c^(n+phi(b)) - a^(n+phi(b))) - (c^n - a^n) is a multiple of
>b.
>
>Therefore (c^(n+phi(b)) - a^(n+phi(b))) mod b = (c^n - a^n) mod b
>
>If that doesn't establish that the period of (c^n - a^n) mod b is a
>factor of phi(b), what does?
Nothing does. I argued the same way to myself, that the period of the component
exponential generators c^n mod b and a^n mod b | phi(b), and so t(c^n - a^n
(mod b)) | phi(b). It simply isn't true. Yes, 0-0=0, but for some other n, b |
c^n - a^n. There's no reason these two powers can't combine with subtraction
because subtraction doesn't associate with exponentiation.
(cn - an) = (c-a)n but
(c^n - a^n) != (c-a)^n
multiplication does associate with exponentation:
(c^n * a^n) = (ca)^n
that's what makes FLT such a hard nut to crack.
I tolerance everything and tolerate everyone.
I love: Dona, Jeff, Kim, Kimmie, Mom, Neelix, Tasha, and Teri, alphabetically.
I drive: A double-step Thunderbolt with 657% range.
I fight terrorism by: Using less gasoline.
- Next message: Phil Carmody: "Re: astonishingly many numbers with abundace 12 and 56"
- Previous message: Han de Bruijn: "Re: Infinite square roots problem - I can't solve it!"
- In reply to: Daniel W. Johnson: "Re: Counterexample to t( (c^n - a^n) mod b ) | phi(b)"
- Next in thread: Daniel W. Johnson: "Re: Counterexample to t( (c^n - a^n) mod b ) | phi(b)"
- Reply: Daniel W. Johnson: "Re: Counterexample to t( (c^n - a^n) mod b ) | phi(b)"
- Messages sorted by: [ date ] [ thread ]
Relevant Pages
|
