## powers mod prime squared

Expand Messages
• Let p be an odd prime. Let g be a generator mod p**2. Let n = g**m mod p**2. Then n**x mod p**2 = (g**m)**x mod (p**2) = (g**(mx)) mod (p**2) = ( g**(
Message 1 of 1 , Sep 13, 2009
Let p be an odd prime.
Let g be a generator mod p**2.
Let n = g**m mod p**2.

Then

n**x mod p**2
= (g**m)**x mod (p**2)
= (g**(mx)) mod (p**2)
= ( g**( mod(mx,p*(p-1) ) ) ) mod (p**2)

Thus, the powers of n mod p**2 is a "cyclic sub-permutation"
of the powers of g mod p**2.

The meaning of "cyclic sub-permutation" is clarified by examples.

Examples for mod 9 and mod 25.

2 is a generator mod 9

Powers of 2 mod 9 are 2,4,8,7,5,1.
powers of 4 mod 9 are 4,7,1,4,7,1.

The even powers of 2 are the powers of 4.

I define (4,7,1,4,7,1) to be a cyclic sub-permutation
of (2,4,8,7,5,1) with index = 2.

Note that a cyclic sub-permutation is not always strictly
a permutation.

That is why I prefix the prefix "sub" to "permutation".

2 is a generator mod 25.

powers of 2 mod 25 are
2,4,8,16,7,14,3,6,12,24,23,21,17,9,18,11,22,19,13,1.

powers of 3 mod 25 are
3,9,2,6,18,4,12,11,8,24,22,16,23,19,7,21,13,14,17,1.

(3,9,2,6,18,4,12,11,8,24,22,16,23,19,7,21,13,14,17,1)
is an example of a cyclic sub-permutation of
(2,4,8,16,7,14,3,6,12,24,23,21,17,9,18,11,22,19,13,1)
with index = 7.

etc.

2 ** 1 mod 9 = 2
2 ** 2 mod 9 = 4
2 ** 3 mod 9 = 8
2 ** 4 mod 9 = 7
2 ** 5 mod 9 = 5
2 ** 6 mod 9 = 1

4 ** 1 mod 9 = 4
4 ** 2 mod 9 = 7
4 ** 3 mod 9 = 1
4 ** 4 mod 9 = 4
4 ** 5 mod 9 = 7
4 ** 6 mod 9 = 1

2 ** 1 mod 25 = 2
2 ** 2 mod 25 = 4
2 ** 3 mod 25 = 8
2 ** 4 mod 25 = 16
2 ** 5 mod 25 = 7
2 ** 6 mod 25 = 14
2 ** 7 mod 25 = 3
2 ** 8 mod 25 = 6
2 ** 9 mod 25 = 12
2 ** 10 mod 25 = 24
2 ** 11 mod 25 = 23
2 ** 12 mod 25 = 21
2 ** 13 mod 25 = 17
2 ** 14 mod 25 = 9
2 ** 15 mod 25 = 18
2 ** 16 mod 25 = 11
2 ** 17 mod 25 = 22
2 ** 18 mod 25 = 19
2 ** 19 mod 25 = 13
2 ** 20 mod 25 = 1

3 ** 1 mod 25 = 3
3 ** 2 mod 25 = 9
3 ** 3 mod 25 = 2
3 ** 4 mod 25 = 6
3 ** 5 mod 25 = 18
3 ** 6 mod 25 = 4
3 ** 7 mod 25 = 12
3 ** 8 mod 25 = 11
3 ** 9 mod 25 = 8
3 ** 10 mod 25 = 24
3 ** 11 mod 25 = 22
3 ** 12 mod 25 = 16
3 ** 13 mod 25 = 23
3 ** 14 mod 25 = 19
3 ** 15 mod 25 = 7
3 ** 16 mod 25 = 21
3 ** 17 mod 25 = 13
3 ** 18 mod 25 = 14
3 ** 19 mod 25 = 17
3 ** 20 mod 25 = 1

4 ** 1 mod 25 = 4
4 ** 2 mod 25 = 16
4 ** 3 mod 25 = 14
4 ** 4 mod 25 = 6
4 ** 5 mod 25 = 24
4 ** 6 mod 25 = 21
4 ** 7 mod 25 = 9
4 ** 8 mod 25 = 11
4 ** 9 mod 25 = 19
4 ** 10 mod 25 = 1
4 ** 11 mod 25 = 4
4 ** 12 mod 25 = 16
4 ** 13 mod 25 = 14
4 ** 14 mod 25 = 6
4 ** 15 mod 25 = 24
4 ** 16 mod 25 = 21
4 ** 17 mod 25 = 9
4 ** 18 mod 25 = 11
4 ** 19 mod 25 = 19
4 ** 20 mod 25 = 1

6 ** 1 mod 25 = 6
6 ** 2 mod 25 = 11
6 ** 3 mod 25 = 16
6 ** 4 mod 25 = 21
6 ** 5 mod 25 = 1
6 ** 6 mod 25 = 6
6 ** 7 mod 25 = 11
6 ** 8 mod 25 = 16
6 ** 9 mod 25 = 21
6 ** 10 mod 25 = 1
6 ** 11 mod 25 = 6
6 ** 12 mod 25 = 11
6 ** 13 mod 25 = 16
6 ** 14 mod 25 = 21
6 ** 15 mod 25 = 1
6 ** 16 mod 25 = 6
6 ** 17 mod 25 = 11
6 ** 18 mod 25 = 16
6 ** 19 mod 25 = 21
6 ** 20 mod 25 = 1

7 ** 1 mod 25 = 7
7 ** 2 mod 25 = 24
7 ** 3 mod 25 = 18
7 ** 4 mod 25 = 1
7 ** 5 mod 25 = 7
7 ** 6 mod 25 = 24
7 ** 7 mod 25 = 18
7 ** 8 mod 25 = 1
7 ** 9 mod 25 = 7
7 ** 10 mod 25 = 24
7 ** 11 mod 25 = 18
7 ** 12 mod 25 = 1
7 ** 13 mod 25 = 7
7 ** 14 mod 25 = 24
7 ** 15 mod 25 = 18
7 ** 16 mod 25 = 1
7 ** 17 mod 25 = 7
7 ** 18 mod 25 = 24
7 ** 19 mod 25 = 18
7 ** 20 mod 25 = 1

8 ** 1 mod 25 = 8
8 ** 2 mod 25 = 14
8 ** 3 mod 25 = 12
8 ** 4 mod 25 = 21
8 ** 5 mod 25 = 18
8 ** 6 mod 25 = 19
8 ** 7 mod 25 = 2
8 ** 8 mod 25 = 16
8 ** 9 mod 25 = 3
8 ** 10 mod 25 = 24
8 ** 11 mod 25 = 17
8 ** 12 mod 25 = 11
8 ** 13 mod 25 = 13
8 ** 14 mod 25 = 4
8 ** 15 mod 25 = 7
8 ** 16 mod 25 = 6
8 ** 17 mod 25 = 23
8 ** 18 mod 25 = 9
8 ** 19 mod 25 = 22
8 ** 20 mod 25 = 1

9 ** 1 mod 25 = 9
9 ** 2 mod 25 = 6
9 ** 3 mod 25 = 4
9 ** 4 mod 25 = 11
9 ** 5 mod 25 = 24
9 ** 6 mod 25 = 16
9 ** 7 mod 25 = 19
9 ** 8 mod 25 = 21
9 ** 9 mod 25 = 14
9 ** 10 mod 25 = 1
9 ** 11 mod 25 = 9
9 ** 12 mod 25 = 6
9 ** 13 mod 25 = 4
9 ** 14 mod 25 = 11
9 ** 15 mod 25 = 24
9 ** 16 mod 25 = 16
9 ** 17 mod 25 = 19
9 ** 18 mod 25 = 21
9 ** 19 mod 25 = 14
9 ** 20 mod 25 = 1

11 ** 1 mod 25 = 11
11 ** 2 mod 25 = 21
11 ** 3 mod 25 = 6
11 ** 4 mod 25 = 16
11 ** 5 mod 25 = 1
11 ** 6 mod 25 = 11
11 ** 7 mod 25 = 21
11 ** 8 mod 25 = 6
11 ** 9 mod 25 = 16
11 ** 10 mod 25 = 1
11 ** 11 mod 25 = 11
11 ** 12 mod 25 = 21
11 ** 13 mod 25 = 6
11 ** 14 mod 25 = 16
11 ** 15 mod 25 = 1
11 ** 16 mod 25 = 11
11 ** 17 mod 25 = 21
11 ** 18 mod 25 = 6
11 ** 19 mod 25 = 16
11 ** 20 mod 25 = 1

12 ** 1 mod 25 = 12
12 ** 2 mod 25 = 19
12 ** 3 mod 25 = 3
12 ** 4 mod 25 = 11
12 ** 5 mod 25 = 7
12 ** 6 mod 25 = 9
12 ** 7 mod 25 = 8
12 ** 8 mod 25 = 21
12 ** 9 mod 25 = 2
12 ** 10 mod 25 = 24
12 ** 11 mod 25 = 13
12 ** 12 mod 25 = 6
12 ** 13 mod 25 = 22
12 ** 14 mod 25 = 14
12 ** 15 mod 25 = 18
12 ** 16 mod 25 = 16
12 ** 17 mod 25 = 17
12 ** 18 mod 25 = 4
12 ** 19 mod 25 = 23
12 ** 20 mod 25 = 1
Your message has been successfully submitted and would be delivered to recipients shortly.