Re: Counterexample to t( (c^n - a^n) mod b ) | phi(b)

From: Doug Goncz (dgoncz_at_aol.com)
Date: 11/20/04 

Date: 20 Nov 2004 11:34:42 GMT

>From: panoptes@iquest.net (Daniel W. Johnson)

>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.

Just typing this out as a learning aid, and for future reference:

Euler's totient theorem:

a^phi(n) == 1 mod n

c^phi(b) == 1 mod b
c^phi(b) - 1 == 0 mod b
b | c^phi(b) - 1
b | x * (c^phi(b) -1)
b | c^n * (c^phi(b) -1)
b | c^n*c^phi(b) - c^n
b | c^(n+phi(b)) - c^n

c^(n+phi(b)) - c^n == 0 mod b
c^(n+phi(b)) mod b = c^n mod b

for all n, so c^n mod b has period t | phi(b).

Got it! Not rote learning, but learning by writing, the way that works for me.
What is immediate for one is immediate for another after study.

>Doug Goncz <dgoncz@aol.com> wrote:

>> 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.

Yes, I finally got my phi function written right, with help. You didn't *quite*
have to bang me over the head with a stick, but I did need to be corrected
three times.

>> 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.

You know, I do need to consider gcd(b,c)>1 because all I am sure of is
gcd(a,b,c)=1. In Fermat's Last Theorem for Amateurs, Paolo Ribenboim writes
(with my comments interposed) on page 2 that:

"If s,y,z are non-zero integers such that x^n + y^n = z^n, if d=gcd(x,y,z) and
x1=x/d, y1=y/d, z1=z/d then x1^n+y1^n=z1^n, (which I totally get) where the
non-zero integers x1, y1, z1 are pairwise relatively prime (which I don't get).
So if we assume that Fermat's equation has a non-trivial solution, it has one
with pairwise relatively prime integers."

I just don't see how factoring out a denominator common to all *three* of x,y,
and z leaves x and y, y and z, and x and z with no common denominator, in
*pairs*.

n,a,b,c = 2,3,4,5 or 2,6,8,10 are solutions to a^n + b^n = c^n. And I've never
seen a (base?) Pythagorean triangle that had a common factor between two edges.

It seems to me x=x1md, y=y1md, z=z1d is possible.

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.

Relevant Pages

  • Re: learning through osmosis
    ... Common for everybody. ... My son was learning drums 6 years ago. ... frustration that interferes with the learning process, ...
    (alt.guitar.beginner)
  • Re: Great SWT Program
    ... GUI, but not learning similar tools later, ... to make emacs easier to use, or vice versa, and isn't a negative (e.g. ... Both assume that you're willing to do a certain amount of learning ... have many keybindings in common. ...
    (comp.lang.java.programmer)
  • Re: Imaginary Action
    ... pretty common. ... I am learning a little more about it ... Some said that landau lifschitz NRQM describes it as well. ... Analytic continuation is a highly useful ...
    (sci.physics)
  • Re: Imaginary Action
    ... pretty common. ... I am learning a little more about it ... Some said that landau lifschitz NRQM describes it as well. ... Analytic continuation is a highly useful technique, and used a lot in physics. ...
    (sci.physics)
  • Re: Y&R- Will Amber End Up Preggers?
    ... Kidding, but the scenario sounds VERY similar, and I'm learning that ... this stuff is a LOT more common than most of us would like to believe. ...
    (rec.arts.tv.soaps.cbs)
Loading