Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I found this problem in my algebra book, but unfortunately, there is no solution included. Here it is:

Let $p$ be a prime, $1 \le k \le p-2$. Show that there exists $x \in \mathbb{Z} \ $ such that $\ x^k \neq 0,1$ (mod $p$).

It looks like a very nice problem, but I have no idea how to solve it.

And a related problem:

Prove that for $k \in \mathbb{N}$:

$\sum _{x \in \mathbb{F}_p ^* }x^k = \begin{cases} 0, \ \ \ \ \ \ \ \ \ \ \ \ p-1 \nmid k\\p-1, \ \ \ \ \ p-1 \ | \ k\end{cases}$

Could you help me?

share|improve this question
    

3 Answers 3

Consider the polynomial $x^k(x^k-1)$. You are asking to show that some $x$ is not a root modulo $p$. That's the same as asking if $x(x^k-1)$ has the same property. But this is a degree $k+1$ polynomial, so it has at most $k+1$ distinct roots. Since $k+1<p$, there is at least one residue mod $p$ that is not a root.

share|improve this answer

For your second question, let $S=1^k+2^k+3^k+\cdots+(p-1)^k$. If $p-1$ divides $k$, then by Fermat's Theorem each of $1^k,2^k,3^k,\dots,(p-1)^k$ is congruent to $1$ modulo $p$, so their sum $S$ is congruent to $p-1$ modulo $p$.

Suppose now that $p-1$ does not divide $k$.

Let $a$ be an integer not divisible by $p$. Then $a,2a,3a,\dots, (p-1)a$ are congruent, in some order, to $1,2,3,\dots,p-1$. So $a^k,(2a)^k, (3a)^k, \dots, ((p-1)a)^k$ are congruent, in some order, to $1^k,2^k,3^k,\dots,(p-1)^k$. Adding up, we find that $$a^k S\equiv S\pmod{p},\quad\text{or equivalently}\quad (a^k-1)S\equiv 0\pmod p.$$ In particular, let $a$ be a primitive root of $p$, that is, an element of order $p-1$ modulo $p$. Since $p-1$ does not divide $k$, it follows that $a^k\not\equiv 1\pmod{p}$, and therefore $a^k-1\not\equiv 0\pmod{p}$. Since $(a^k-1)S\equiv 0\pmod{p}$, it follows that $S\equiv 0\pmod{p}$.

Another way: If $g$ is a primitive root of $p$, then our sum is congruent to $g^k+g^{2k}+g^{3k}+\cdots+g^{(p-1)k}$. The last term is congruent to $1^k$, so it looks a little nicer to write $$S\equiv 1+g^k+g^{2k}+\cdots+g^{(p-2)k}\pmod p.$$ Multiply each side of the above congruence by $1-g^k$, and observe the cancellations. We get $$S(1-g^k)\equiv 1-g^{p-1)k}\pmod{p}.$$ The right-hand side is congruent to $0$ modulo $p$, by Fermat's Theorem. Since $g$ is a primitive root of $p$, and $p-1$ does not divide $k$, it follows that $1-g^k\not\equiv 0\pmod{p}$, and therefore $S\equiv 0\pmod{p}$. Note that essentially we have used the formula for the sum of a finite geometric progression.

share|improve this answer

For the first question,

$x^k\equiv0\pmod p\iff x\equiv 0\pmod p$

Now, we can always find one $x$ (in fact, $p-1$ of them) which is relatively prime to $p$

For $x^k\not\equiv1\pmod p,$ it is sufficient to prove that there is at least one $x$ with order $p-1$ i.e., there is at least one primitive root $\pmod p,$ the proof is available here and here.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.