1. ## Simple polynomial problem?

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!) ?

2. 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 $\displaystyle G$ is cyclic of order $\displaystyle n$, generated by $\displaystyle x$, and $\displaystyle m|n$, then $\displaystyle x^m$ is not a generator of $\displaystyle G$. In fact the condition $\displaystyle m|n$ is stronger than required - it suffices that $\displaystyle (m,n)>1$, because then $\displaystyle x^m$ has order $\displaystyle \frac{n}{(m,n)}<n$.

3. Originally Posted by Nivla
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

4. 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.

### solution to simplepolynomial problens

Click on a term to search for related topics.