Re: Counterexample to t( (c^n - a^n) mod b ) | phi(b)
From: Daniel W. Johnson (panoptes_at_iquest.net)
Date: 11/19/04
- Next message: Daniel W. Johnson: "Re: Counterexample to t( (c^n - a^n) mod b ) | phi(b)"
- Previous message: Stephen Harris: "Re: Zenkin's paper on Cantor (reply of Dr. Zenkin)"
- In reply to: Doug Goncz : "Re: Counterexample to t( (c^n - a^n) mod b ) | phi(b)"
- Next in thread: Doug Goncz : "Re: Counterexample to t( (c^n - a^n) mod b ) | phi(b)"
- Reply: Doug Goncz : "Re: Counterexample to t( (c^n - a^n) mod b ) | phi(b)"
- Messages sorted by: [ date ] [ thread ]
Date: Fri, 19 Nov 2004 14:12:48 -0500
Doug Goncz <dgoncz@aol.com> wrote:
> 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.
Right. You gave gcd(a,b,c)=1. You did not give
gcd(a,b)=gcd(a,c)=gcd(b,c)=1. Consider a=6, b=10, c=15. Then
gcd(b,c)=5 but gcd(a,b,c)=1.
> 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))
No. Euler's totient theorem gives us b | c^(phi(b)) - 1
Since c^(n+phi(b))-c^n = c^n*(c^(phi(b)) - 1), the result is immediate.
> 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).
That's not a counterexample, as has already been pointed out to you.
7^n - 5^n (mod 6) is 0 for even n and 2 for odd n. That's periodic with
a period of 2, just like 5^n mod 6, and 2 divides phi(6) = 2. (7^n mod
6 actually has a period of 1.)
> >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
Multiplication does distribute over subtraction, which is all that
matters.
More generally, suppose f(n) and g(n) both have periods that divide k.
In other words, f(n+k) - f(n) and g(n+k) - f(n) are 0 for all n. In
this case, f(n) = c^n mod b and g(n) = a^n mod b, and the period k is
phi(b). Define h(n) = f(n) - g(n). We then have, for all n:
h(n+k) - h(n) = (f(n+k) - g(n+k)) - (f(n) - g(n))
= f(n+k) - f(n) - g(n+k) + g(n)
= (f(n+k) - f(n)) - (g(n+k) - g(n))
= 0 - 0
= 0
Q.E.D.
-- Daniel W. Johnson panoptes@iquest.net http://members.iquest.net/~panoptes/ 039 53 36 N / 086 11 55 W
- Next message: Daniel W. Johnson: "Re: Counterexample to t( (c^n - a^n) mod b ) | phi(b)"
- Previous message: Stephen Harris: "Re: Zenkin's paper on Cantor (reply of Dr. Zenkin)"
- In reply to: Doug Goncz : "Re: Counterexample to t( (c^n - a^n) mod b ) | phi(b)"
- Next in thread: Doug Goncz : "Re: Counterexample to t( (c^n - a^n) mod b ) | phi(b)"
- Reply: Doug Goncz : "Re: Counterexample to t( (c^n - a^n) mod b ) | phi(b)"
- Messages sorted by: [ date ] [ thread ]
Relevant Pages
|
