Given that 2 is a generator of cyclic gp U(25), find all generators of U(25) listed as powers of 2?

Answer 1

Theory tells us that U(25) is a group of order 20
and that there are φ(20) = 8 generators.
Let's try to find them first, then we'll list them as
powers of 2.
If x is a generator, we want
x^20 = 1(mod 25), but x^n.ne. 1(mod 25) for n < 20.
Let's try to solve
x^20-1 =0(mod 25)
(x^10-1)(x^10+1)= 0(mod 25)
There's a "semi-zero divisor law" for congruences
mod p².
If ab = 0(mod p²) then either a = 0 or b = 0
or a = b = p(mod p²).
In our case, we cannot have both factors equal to 0(mod 5)
simultaneously. Further, if x^10 = 1(mod 25) then
x cannot have order 20 mod(25).
So all our generators must satisfy x^10+1 = 0(mod 25).
So how do we solve this congruence?
Let's make use of Hensel's lemma. (Stated at the
end of this post.)
With some work we find that
x^10 + 1 = (x-2)^5* (x-3)^5 mod 5.
and the derivative of x^10 + 1, 10x^9 = 0(mod 5)
at 2 and 3.
Since 2^10+1 and 3^10 + 1 are both 0(mod 25)
2 + 5t
and 3+ 5t,
0 <= t <=4,
are all solutions of x^10+1 = 0(mod 25)
So the possible generators are
2 7 12 17 22
and
3 8 13 18 23.
But not all of these have order 20 mod 25.
Note that 7^2 = -1 and 7^4 = 1(mod 25),
so 7 has order 4. Similarly, 18 = -7 has order 4.
So our generators are
2 12 17 22
3 8 13 23.
With the aid of PARI I checked that all these do indeed
have order 20.
Now let's get the powers of 2 and match these.
2^1 = 2
2^2 = 4
2^3 = 8
2^4 = 16
2^5 = 7
2^6 = 14
2^7 = 3
2^8 = 6
2^9 = 12
2^10 = 24
2^11 = 23
2^12 = 21
2^13 = 17
2^14 = 9
2^15 = 18
2^16 = 11
2^17 = 22
2^18 = 19
2^19 = 13
2^20 = 1
So let's put the lists together:
Generators 2 12 17 22 3 8 13 23
Power of 2: 1 9 13 17 7 3 19 11

Hensel's Lemma:
A version of the lemma for p-adic fields is as follows. Let f(x) be a polynomial with integer coefficients, k an integer not less than 2 and p a prime number. Suppose that r is a solution of the congruence

f(r) \equiv 0 \pmod{p^{k-1}}.\,

If f'(r) \not\equiv 0 \pmod{p}, then there is a unique integer t, 0 ≤ t ≤ p-1, such that

f(r + tp^{k-1}) \equiv 0 \pmod{p^k}\,

with t defined by

tf'(r) \equiv -(f(r)/p^{k-1}) \pmod{p}.\,

If, on the other hand, f'(r) \equiv 0 \pmod{p}, and in addition, f(r) \equiv 0 \pmod{p^k}, then

f(r + tp^{k-1}) \equiv 0 \pmod{p^k}\,

for all integers t.

Also, if f'(r) \equiv 0 \pmod{p}\, and f(r) \not\equiv 0 \pmod{p^k}, then f(x) \equiv 0 \pmod{p^k}\, has no solution for any x \equiv r \pmod{p^{k-1}}.\,
Note: \equiv is the TeX equivalent of the congruence sign.

Answer 2

U(25) is a cyclic group of order Phi(25) = 20, and thus it has Phi(20) = 8 generators.
Since 2^10 = -1 (mod 25) 2 indeed is a generator of U(25), and thus the other generators will be 2^k, with (k,20) = 1, namely: k is in {1,3,7,9,11,13,17,19}.
For example, 2^3 = 8 is a generator, and 2^7 = 128 = 3 (mod 25) is another, and 2^11 = 2^7*2^4 = 3*16 = 23 (mod 25) another one, etc.

Regards
Tonio