Simple polynomial problem?

Nivla · #1 $Old$ November 4th, 2009, 10:07 PM

A problem from G.E. Andrews's "Number Theory":

Suppose g is a primitive root modulo p (a prime) and m | p-1, where (0<m<p-1). How many integral solutions are there of the congruence
x^m - g "congruent to" 0 (mod p).

Proposed solution:

Assume there is at least one such x.

p ~|g since g is a primitive root.
Therefore p ~| x ^ m and p ~| x.

p ~| x implies x ^ p-1 "congruent to" 1 (Euler's Theorem).

mk= p-1 for some k. (hyp)

x ^ mk "congruent to" 1

x ^ m "congruent to" g. (hyp)

x ^ mk "congruent to" g ^ k. (raise to a power)

g ^ k "congruent to" 1. (Congruence is an equivalence rel.)

k < p-1

g is not a primitive root, since g does not belong to p-1.

Conclusion: there is no x such that x^m "congruent to" g.

Is this conclusion acceptable (or almost acceptable!) ?

Bruno J. · #2 $Old$ November 4th, 2009, 10:34 PM

Very good. I'm not sure I understand your notation very well but the solution is correct. In group-theoretic terms, what you have shown is that if a group $G$ is cyclic of order $n$ , generated by $x$ , and $m|n$ , then $x^m$ is not a generator of $G$ . In fact the condition $m|n$ is stronger than required - it suffices that $(m,n)>1$ , because then $x^m$ has order $\frac{n}{(m,n)}<n$ .

tonio · #3 $Old$ November 4th, 2009, 10:48 PM

Quote:

Originally Posted by Nivla $View Post$

A problem from G.E. Andrews's "Number Theory":

Suppose g is a primitive root modulo p (a prime) and m | p-1, where (0<m<p-1). How many integral solutions are there of the congruence
x^m - g "congruent to" 0 (mod p).

Proposed solution:

Assume there is at least one such x.

p ~|g since g is a primitive root.
Therefore p ~| x ^ m and p ~| x.

p ~| x implies x ^ p-1 "congruent to" 1 (Euler's Theorem).

mk= p-1 for some k. (hyp)

x ^ mk "congruent to" 1

x ^ m "congruent to" g. (hyp)

x ^ mk "congruent to" g ^ k. (raise to a power)

g ^ k "congruent to" 1. (Congruence is an equivalence rel.)

k < p-1

g is not a primitive root, since g does not belong to p-1.

Conclusion: there is no x such that x^m "congruent to" g.

Is this conclusion acceptable (or almost acceptable!) ?

More than acceptable: it is, as far as I can see, true.

Tonio

Nivla · #4 $Old$ November 5th, 2009, 01:36 AM

Bruno J.: Thanks for the group-theoretic reference! In this case, the order n is p-1, the number of members of the reduced residue set: {g, g^2, g^3, ... , g^p-1} (I believe).

I have to admit my need to refresh my memory on the order of a cyclic group, but I follow you.