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

From: Phil Carmody (thefatphil_demunged_at_yahoo.co.uk)
Date: 11/18/04 

Date: 18 Nov 2004 17:41:00 +0200

dgoncz@aol.com ( Doug Goncz ) writes:

> >From: dgoncz@aol.com ( Doug Goncz ) (Me)
>
> >phi(6)=2 (5 and 1 do not divide 6)
>
> Neither does 4.
>
> I just misspelled ph(b)=3, it wasn't calculated correctly.
>
> So does the period of (c^n-a^n) mod b divide phi(b) or doesn't it?
>
> I say it doesn't always divide phi(b).

Don't just "say", prove.

(17:38) gp > for(a=0,5,for(b=0,5,print1(a" "b" : ");for(n=1,6,print1(" "(a^n-b^n)%6));print()))
0 0 : 0 0 0 0 0 0
0 1 : 5 5 5 5 5 5
0 2 : 4 2 4 2 4 2
0 3 : 3 3 3 3 3 3
0 4 : 2 2 2 2 2 2
0 5 : 1 5 1 5 1 5
1 0 : 1 1 1 1 1 1
1 1 : 0 0 0 0 0 0
1 2 : 5 3 5 3 5 3
1 3 : 4 4 4 4 4 4
1 4 : 3 3 3 3 3 3
1 5 : 2 0 2 0 2 0
2 0 : 2 4 2 4 2 4
2 1 : 1 3 1 3 1 3
2 2 : 0 0 0 0 0 0
2 3 : 5 1 5 1 5 1
2 4 : 4 0 4 0 4 0
2 5 : 3 3 3 3 3 3
3 0 : 3 3 3 3 3 3
3 1 : 2 2 2 2 2 2
3 2 : 1 5 1 5 1 5
3 3 : 0 0 0 0 0 0
3 4 : 5 5 5 5 5 5
3 5 : 4 2 4 2 4 2
4 0 : 4 4 4 4 4 4
4 1 : 3 3 3 3 3 3
4 2 : 2 0 2 0 2 0
4 3 : 1 1 1 1 1 1
4 4 : 0 0 0 0 0 0
4 5 : 5 3 5 3 5 3
5 0 : 5 1 5 1 5 1
5 1 : 4 0 4 0 4 0
5 2 : 3 3 3 3 3 3
5 3 : 2 4 2 4 2 4
5 4 : 1 3 1 3 1 3
5 5 : 0 0 0 0 0 0

Either constant (period 1) or alternating (period 2).

Phil 

-- 
... one Marine noticed one of the prisoners was still breathing. A Marine 
can be heard saying on the pool footage provided to Reuters Television: 
"He's fucking faking he's dead. He faking he's fucking dead."
"The Marine then raises his rifle and fires into the man's head. 
The pictures are too graphic for us to broadcast," Sites said.