A079327

[Gottfried Helms]

I wrote:
> Jon Perry schrieb:
> > 
> > Regarding;
> > 
> > Lowest exponent of k such that b^k mod n = b^(n-1) mod n
> > 
> Hi Jon, 
>  did you ask for more explanation?
> 
> Gottfried Helms

Let b=2, and n=5.
Then b^k mod n defines a cycle of

   1,2,4,3,1,2,4,3,...  for k=0..oo

the length C of the cycle is 4.

Now for any odd n>1 there is a specific C.
* For primes n the cycle-length is a integer part
  of n-1, thus b^C mod n = 1. This is also true for
  some base-b-pseudoprimes
* For composite n their C is *not* an integral part of n-1,
  for instance for n=9 the cycle is

      1,2,4,8,7,5,1,2,4,8,7,5,1,...

  with a cycle-length C = 6.

     2^8 mod 9 

    now is 
     2^(8 mod C) mod 9

       and this is
           2^2

Now it seems, that for all bases<>n this is the same.

Let b=7, n=5. 
  The cycle b^k mod n is

     1,2,4,3,1,2,4,3,1,... 

  with the cycle-length of C= n-1=4
  So again

     7^C mod 5 = 1  = 7^0 mod 5

     and this is true for all bases<>n.

  Now for n=9 it is

     1,7,4,1,7,4,...

  with the cycle-length C=3

     7^8 mod 9 

  now is
     7^(8 mod 3) mod 9

  and this is
     7^2 mod 9

  Again, for n=9 is b^(n-1) mod 9 = b^2. (note, that the
  cycle-length itself is NOT the same as with base 2)

The generalizing is that

  for all b and all n

     b^((n-1) mod C)  mod n = b^(n-1) mod n 

which also says something about a fixed relation between C
and (n-1) over all bases b<>n besides of primality testing
according to Fermat.

It can nicely be seen in the table of moduli according to
the little-fermat-test with different bases. (see appendix)

I find this surprising, and came across it, when I tried to
find a calculus for the handling of powers mod n, for instance
b^(b^(b...))) mod n. 

Gottfried Helms


				base							
	|		|	1	2	3	4	5	6	7	8
------------------------------------------------------------------------------------------
k (b^k=rmd)     n                rmd = b^(n-1) mod n
------------------------------------------------------------------------------------------
0	|	2	|	1	0	1	0	1	0	1	0
0	|	3	|	1	1	0	1	1	0	1	1
3	|	4	|	1	0	3	0	1	0	3	0
0	|	5	|	1	1	1	1	0	1	1	1
1	|	6	|	1	2	3	4	5	0	1	2
0	|	7	|	1	1	1	1	1	1	0	1
3	|	8	|	1	0	3	0	5	0	7	0
2	|	9	|	1	4	0	7	7	0	4	1
1	|	10	|	1	2	3	4	5	6	7	8
0	|	11	|	1	1	1	1	1	1	1	1
3	|	12	|	1	8	3	4	5	0	7	8
0	|	13	|	1	1	1	1	1	1	1	1
1	|	14	|	1	2	3	4	5	6	7	8
2	|	15	|	1	4	9	1	10	6	4	4
7	|	16	|	1	0	11	0	13	0	7	0
0	|	17	|	1	1	1	1	1	1	1	1
5	|	18	|	1	14	9	16	11	0	13	8
0	|	19	|	1	1	1	1	1	1	1	1
3	|	20	|	1	8	7	4	5	16	3	12
2	|	21	|	1	4	9	16	4	15	7	1
1	|	22	|	1	2	3	4	5	6	7	8
0	|	23	|	1	1	1	1	1	1	1	1
3	|	24	|	1	8	3	16	5	0	7	8
4	|	25	|	1	16	6	6	0	21	1	21
1	|	26	|	1	2	3	4	5	6	7	8
8	|	27	|	1	13	0	7	16	0	4	10
3	|	28	|	1	8	27	8	13	20	7	8