For p=2 take n=5. Let now p be odd. We have p^p-1=(p-1)(1+p+..+p^{p-1}}. The second bracket is odd and is not equal 1 modulo p^2. Then there exists its prime divisor q, which is odd and not of form k*p^2+1. Lets prove that q satisfies condition. If n^p=p (mod q), then (n^p)^p=p^p=1 (mod q), so n^{p^2}=1 (mod q). Since n^{q-1}=1 (mod q), we have n^gcd(q-1,p^2)=1 (mod q). But q-1 is not divisible by q^2, then gcd(q-1,p^2) is p or 1. so, n^p=1 (mod q) -- a contradiction, unless p-1 is divisible by q. But the 1+p+..+p^{p-1}=p (mod p-1), so coprime with p-1.

What follows is just the construction Fedor Petrov provided. Our excuse for this post is that it'll attempt to show that this choice of q is in fact quite 'natural'. Thus we are just trying to solve the congruence x^p = p (mod q). When does this have no solution? By Euler's criterion, or much more cutely by summing up (n^p -p)^(q-1) over n lying in Z/qZ, we observe that the above congruence has no solution if and only if the following conditions are met: 1) q = 1(mod p) 2)p^ ((q-1)/p) not equal to 1 (mod q) Thus the problem is equivalent to proving the existence of a prime q satisfying 1) and 2). So it almost seems like a special case of the decidedly non-elementary Dirichlet's theorem for primes in Arithmetic progression! But there is an elementary proof of this theorem for the mk+1 case and this falls in that case...more exactly one can (easily)prove that for any c,d integers,(c,d) not equal to (3,2), c^d - 1 has a prime divisor of the form kd+1. The proof begins with the observation that any prime dividing c^d -1 and not dividing c^h - 1 for all h properly dividing d must be of the form kd+1;to complete the proof one has to show that such a prime exists.The existence of such a prime is a matter of simple inequalities. In our problem d = p, and h can only be 1. So, there are not many other ways to proceed except to choose c, and then choose any prime q that divides c^p -1, does not divide c-1 and hope(here's where the 'suitability' of the c comes in) that p^((q-1)/p) is not 1 mod q. Since we dont have many numbers to play with, the first guess would be c=p, which works. Finally, since a bit of generalization can't hurt, the same constuction, with a^p-1 instead of p^p -1, proves the following result: Let p be an odd prime and a be an integer such that p^2 does not divide a^p - a. Then there exists a prime q such that n^p - a is not divisible by q for any integer n. -Abhishek Saha

Let K be the splitting field over Q of x^p-p . This is Galois of order p(p-1). Chebotarev density gives Frobenius elements of order p. Not elementary, but at the heart of the question

Quote: n^{p^2}=1 (mod q). Since n^{q-1}=1 (mod q), we have n^gcd(q-1,p^2)=1 (mod q). why n^gcd(q-1,p^2) = 1 (mod q)? i cannot see it clearly.

To the last guest: gcd of two positive integers is their linear combination with integer coefficients. So, if n^A=1 (mod p) and n^B=1 (mod p), then n^gcd(A,B)=n^(k*A+l*B)=1^k*1^l=1 (mod p). Never mind that l or k may be negative.

Jayanta wrote: Let K be the splitting field over Q of x^p-p . This is Galois of order p(p-1). Chebotarev density gives Frobenius elements of order p. Not elementary, but at the heart of the question That sounds intriguing, but since I have no idea what "Chebotarev density" or "Frobenius elements" are, it's completely lost on me. Do you think you could possibly give me some idea of what that is? I do know some Galois theory.

I started writing out something on the Chebotarev stuff.... and decided at the end that the best way is to give some references. Two books that come to mind are Local Fields by Jean-Pierre Serre and Algebraic Number Theory by Serge Lang. Here is a naive/simplistic way of looking at it: lets suppose K / Q finite Galois with Galois group G, and suppose that K splits the irreducible polynomial $f$ (with Q coeffs). We can look at the reduction mod p of f and look at its Galois group over F_p --- this will work for primes outside a finite set (called ramified primes). And over F_p, we know that the Galois group is cyclic with a canonical generator---the Frobenius map which raises elements to the p-th power. It turns out that these infact lift to elements in the Galois group G, and these are the Frobenius elements. Chebotarev density then says that each conjugacy class in G contains lots of Frobenius elements. So what does this have to do with the original problem? There, we had G a non-abelian group of order p(p-1). Look at the conjugacy class given by an element of order of p. Unravelling what Chebotarev says gives us lots of primes q such that the splitting field of $X^p-p$ over F_q is of degree p. Which is precisely what we want! The same method also deals with any irreducible polynomial f of prime degree... there is a prime q which does not divide f(n) for any integral n. Jayanta

Thank you very much! You've certainly given me food for thought.

Anonymous wrote: Never mind that l or k may be negative. why does it hold when l or k is negative? i just confused with this.

Because the division is possible modulo p, aswell as multyplication, if we divide to the number which is not a factor of p (or consider all calculations in the field of residues modulo p).

A circle has p congruent sectors where p is a prime. In how many ways these p sectors can be coloured with n colours if for several (maybe even all) sectors the same colouring is valid. Two colourings are considered as different if they don't cover each other by means of a rotation of the circle. Prove the theorem by Fermat: If p is a prime then n^p-n is divisible for each n by p ! Is this problem anyhow related to IMO2003/6 ?

abhisaha wrote: Thus we are just trying to solve the congruence $x^p = p \pmod{q}$. When does this have no solution? By Euler's criterion, or much more cutely by summing up $(n^p -p)^{(q-1)}$ over $n$ lying in $\mathbb{Z}/q\mathbb{Z}$, we observe that the above congruence has no solution if and only if the following conditions are met: 1) $q = 1\pmod{p}$ 2) $p^{(\frac{q-1}{p})} \not\equiv 1 \pmod{q}$ How does this conclusion follow from either of the two methods (Euler's Criterion and/or the sum) that the quoted poster mentioned?

supercomputer wrote: abhisaha wrote: Thus we are just trying to solve the congruence $x^p = p \pmod{q}$. When does this have no solution? By Euler's criterion, or much more cutely by summing up $(n^p -p)^{(q-1)}$ over $n$ lying in $\mathbb{Z}/q\mathbb{Z}$, we observe that the above congruence has no solution if and only if the following conditions are met: 1) $q = 1\pmod{p}$ 2) $p^{(\frac{q-1}{p})} \not\equiv 1 \pmod{q}$ How does this conclusion follow from either of the two methods (Euler's Criterion and/or the sum) that the quoted poster mentioned? I assume that you looked up what Euler's Criterion is, and found something relating to quadratic residues. Well, what we're using here is a generalization of that: how can we tell if something has a $p$-th root modulo $q$. Let us first get the first condition, that $q \equiv 1 \pmod{p}$. Well, let's assume that $q \not\equiv 1 \pmod{p}$. We'll now show that every single number has a $p$-th root modulo $q$. Suppose we had two $x \not\equiv y \pmod{q}$ such that $x^p \equiv y^p \pmod{q}$. Multiply both sides by $y^{-p}$ to get $(xy^{-1})^p \equiv 1 \pmod{q}$, which means that $\text{ord}_q(xy^{-1}) | \gcd{(p, q-1)}$, but because $q-1$ and $p$ are relatively prime, we have $x \equiv y \pmod{q}$, contradiction. So that means, if we consider the set numbers $1^p, 2^p, 3^p, ..., (q-1)^p$, no two of them are the same, which means that every residue has a $p$-th root...which of course would imply that $n^p \equiv p \pmod{q}$ has a solution. Okay so now we know that $q \equiv 1 \pmod{p}$. The second one is now very similar to Euler's Criterion for quadratic residues. Suppose there exists some integer $r$ such that $r^p \equiv p \pmod{q}$. Then, raising both sides to the $\frac{q-1}{p}$ -th power, we get $r^{q-1} \equiv 1 \equiv p^{\frac{q-1}{p}} \pmod{q}$, so if $p^{\frac{q-1}{p}} \not\equiv 1 \pmod{q}$, then $n^p \equiv p \pmod{q}$ cannot have a solution. Now to prove it the other way, that if $x^p \equiv p \pmod{q}$ doesn't have a solution, then $p^{\frac{q-1}{p}} \not\equiv 1 \pmod{q}$. Well, the number of solutions to $n^{\frac{q-1}{p}} \equiv 1 \pmod{q}$ is at most $\frac{q-1}{p}$ since $q$ is prime. Suppose again we have $x^p \equiv y^p \pmod{q}$ so that $(xy^{-1})^p \equiv 1 \pmod{q}$. The order of $xy^{-1}$ is either $1$ in which case $x \equiv y$ or $p$. Hence, there are $p$ values that $xy^{-1}$ can take on, which means that given a certain $x$ such that $x^p \equiv \text{something} \pmod{q}$, we have $p-1$ other numbers $y$ such that $y^p \equiv x^p \pmod{q}$. Suppose $r_1, r_2, ..., r_m$ are integers that have a $p$-th root. Furthermore, we know that each one has exactly $p$ roots. Therefore, $mp = q-1$, so $m = \frac{q-1}{p}$, so there are $\frac{q-1}{p}$ numbers that are perfect $p$-th powers modulo $q$. Therefore, the congruence $x^{\frac{q-1}{p}} \equiv 1 \pmod{p}$ is satisfied if and only if $x$ is a perfect $p$-th power. And, of course, letting $x = p$, we see that there exists an integer $n^p \equiv p \pmod{p}$ if and only if $p^{\frac{q-1}{p}} \equiv 1 \pmod{q}$. Hope that answers your question about Euler's Criterion. As for the summing $(n^p - p)^{q-1}$: from FLT, we know that $x^{q-1} \equiv 1 \pmod{q}$ UNLESS $q|x$. So if we assume that for all $n$, $n^p - p$ is not divisible by $q$, then $(n^p - p)^{q-1} \equiv 1 \pmod{q}$, so when we sum over $n$ from $1$ to $q-1$, we should get $q-1$ modulo $q$. By expanding $(n^p - p)^{q-1}$ and reducing everything, we get the same conditions as mentioned above. Try it yourself!

Surprisingly easy just take a prime divisor of $ \frac{p^p-1}{p-1} $ that is not 1 mod $p^2$ There were some little details

Since I'm in the business of learning about Frobenius elements, let's write out the details of the solution using the Chebotarev Density Theorem. First, we draw the tower of fields \[ \mathbb Q \subseteq \mathbb Q(\sqrt[p]{p}) \subseteq K \] where $K$ is the splitting field of $f(x) = x^p-p$. Let $E = \mathbb Q(\sqrt[p]{p})$ for brevity and note it has degree $[E:\mathbb Q] = p$. Let $G = \operatorname{Gal}(K/\mathbb Q)$, note that it has order $[K:\mathbb Q]$ divisible by $p$. Hence by Sylow's Theorem we can find a $\sigma \in G$ of order $p$. By Cheboratev, there exists infinitely many rational (unramified) primes $q \neq p$ and primes $\mathfrak Q \subseteq \mathcal O_K$ above $q$ such that $\operatorname{Frob}_{\mathfrak Q} = \sigma$. (Yes, that's an uppercase Gothic $Q$. Sorry.) We claim that all these $q$ work. We know that the factorization of $f \pmod q$ is controlled by the action of $\sigma = \operatorname{Frob}_{\mathfrak Q}$ on a set of $p$ cosets. But $\sigma$ has prime order $p$ in $G$! So all the lengths in the cycle structure have to divide $p$. Thus the possible factorization patterns of $f \pmod q$ are \[ p= \underbrace{1 + 1 + \dots + 1}_{\text{$p$ times}} \quad\text{or}\quad p = p. \] EDIT: math154 points out that my original finish doesn't work, but the following does. We rule out the $p = 1 + \dots + 1$ case now. Since $q$ is unramified, $\sigma$ acts in the same way on the roots of $f \pmod q$ as it does on the roots of $f$. So if $\sigma$ was the identity (all cycles have length $1$) on the roots of $f \pmod q$, then it would necessarily be the identity on the roots of $f$, full stop. But then $\sigma$ is the identity in $K$ (since $K$ is the splitting field), contradicting the hypothesis that $\sigma$ should have order $p$.

My solution $\mathrm{First\,we\,can\,see\,that\,}P=p^{p-1}+...+p+1\equiv p+1[p^{2}]\Rightarrow \exists q\in \mathbb{P}\\\mathrm{such\,that\,}q|P,\,\mathrm{and\,}q\not\equiv 1[p^{2}],\,\mathrm{we\,claim\,that\,}q\,\mathrm{is\,not\,divide\,}n^{p}-p\,\forall n\in \mathbb{N}\\\mathrm{indeed,\,assume\,that\,}q|n^{p}-p\,\mathrm{for\,some\,}n,\,\mathrm{now\,we\,have\,clearly\,}q\neq p,\,\mathrm{and}\\ p\not\equiv 1[q]\,(\mathrm{otherwise\,}p\equiv P\equiv 0[q])\Rightarrow q|P\Leftrightarrow q|P(p-1)=p^{p}-1\Rightarrow \\ d=ord_{q}(p)|p,\,\mathrm{but\,}d\neq 1\Rightarrow d=p\Rightarrow p|q-1,\,\mathrm{now\,we\,write\,}q=pm+1\\\mathrm{by\,the\,definition\,of\,}q\,\mathrm{we\,get\,}p\,\mathrm{is\,is\,not\,a\,divisor\,of\,}m,\,\mathrm{but\,in\,other\,hand,}\\ p^{m}\equiv n^{pm}\equiv n^{q-1}\equiv 1[q]\Rightarrow p|m\Rightarrow \Leftarrow !!,\,\mathrm{so\,we\,are\,done\;\blacklozenge }$

Lemma: There exists a prime $q$ such that: $q\mid \frac{p^p-1}{p-1}$ $p^2\nmid q-1$. Proof: Note that $\frac{p^p-1}{p-1}\equiv 1+p\pmod{p^2}$, so we are done; if every prime factor was $1\pmod{p^2}$ then we would get a contradiction. So, we have a prime with $v_p(q-1)\le 1$ and $q\mid \frac{p^p-1}{p-1}$. The latter condition means $\text{ord}_q (p)=p$. Thus, $p\mid q-1$. It is evident that this means $q\nmid p^{\frac{q-1}{p}}-1$ as $p\nmid \frac{q-1}{p}$. We claim that this prime $q$ has the property that it never divides $n^p-p$ for any $n$. Indeed, suppose $n^p\equiv p\pmod{q}$. Then $n^{q-1}\equiv p^{\frac{q-1}{p}}\equiv 1\pmod{q}$, which is a contradiction, so we are done.

iandrei wrote: Let $p$ be a prime number. Prove that there exists a prime number $q$ such that for every integer $n$, the number $n^p-p$ is not divisible by $q$. For $p=2$ pick $q=5$; since $2$ is quadratic non-residue mod $5$, we're good to go. Now let $p$ be an odd prime. Let $N=\frac{p^p-1}{p-1}=p^{p-1}+\dots+p+1$. Observe that $\gcd(N, p-1)=1$ and $N \not \equiv 1 \pmod{p^2}$. It is possible to pick a prime $q \mid N$ with $v_p(q-1)=1$. Then we claim that this prime $q$ works. Suppose $n \in \mathbb{Z}$ with $n^p \equiv p \pmod{q}$. Then $$n^{p^2} \equiv p^p \equiv 1 \pmod{q}.$$So if $d$ is the order of $n$ mod $q$, then $d \mid \gcd(p^2, q-1)$. Consequently, $d \in \{1,p\}$ forcing $q \mid p-1$, a contradiction! $\blacksquare$

can i please know why we think about using p^p-1/p-1

Existence of such prime: Since $$p+1\equiv 1+p+p^2+p^3+\dots+p^{p-1}=\tfrac{p^{p}-1}{p-1} \pmod{p^2}$$we must have a prime $r$ such that $\tfrac{p^{p}-1}{p-1}\equiv 0\pmod r$ and $p^2\nmid r-1.$ $\blacksquare$ This prime works: Assume the contrary then $$n^p\equiv p\pmod r \iff 1\equiv p^{\tfrac{r-1}{p}}\pmod r.$$This forces $r\equiv 1\pmod{p^2}$ due to order reasons, impossible. $\blacksquare$

If $p=2$, then take $q=3$. Otherwise, consider prime divisors of $p^{p-1}+p^{p-2}+\cdots+1$. If all of them are congruent to $1 \pmod{p^2}$, then $p^{p-1}+p^{p-2}+\cdots+1 \equiv 1 \pmod{p^2}$, a contradiction. Thus, there must be a prime divisor not congruent to $1 \pmod{p^2}$. Take $q$ to be that prime. We have $q \mid (p-1)(p^{p-1}+p^{p-2}+\cdots+1)=p^p-1$, so $\operatorname{ord}_q(p) \mid p$. If $\operatorname{ord}_q(p)=1$, then $p \equiv 1 \pmod{q}$, but that means $p^{p-1}+p^{p-2}+\cdots+1 \equiv p \not\equiv 0 \pmod{q}$, a contradiction. Therefore, we have $\operatorname{ord}_q(p)=p$. Notice that $p$ not being a $p$th power $\!\!\!\mod{q}$ is equivalent to $p^\frac{q-1}{p} \not\equiv 1 \pmod{q}$. But notice by assumption that $\operatorname{ord}_q(p)=p \nmid \tfrac{q-1}{p}$, so we're done.

for some prime $q$ let $g$ be a primitive root modulo $q$ and $n \equiv g^\alpha$ , $p\equiv g^\beta$ so $n^p \equiv p \pmod{q}$ or $g^{\alpha p} \equiv g^\beta \pmod{q}$ and it means $\alpha p \equiv \beta \pmod{q-1}$ now let $q = pk+1$ then $\alpha p \equiv \beta \pmod{pk}$ so $p | c$ it's enough find $q$ such that $p \nmid c$. note that $ord_q(p) = \frac{q-1}{gcd(c,q-1)}$ if $v_p(q-1)=1,p|ord_q(p)$ then $p\nmid c$ we will show that one of prime factors of $\Phi_p(p)$ has this properties ($\Phi_p(x) = \frac{x^p-1}{x-1}$) - $\color{blue} q\equiv 1 \pmod{p} : $ we know that all prime factors of $\Phi_p(x)$ are $pk+1$ or $p$ but $p\nmid \Phi_p(p)$ - $\color{blue} p \mid ord_q(p) : $ so $q\nmid p-1$ ( because isn't possible $p\equiv 1 \pmod{q},q\equiv 1 \pmod{p}$) so $p^p \equiv 1 \pmod{q}$ and $ord_q(p) \mid p$ but $ord_q(p) \not =1$ so $ord_q(p) = p$ - $\color{blue} v_p(q-1) = 1 : $ let all prime factors of $\Phi_p(x)$ be on form $p^2k+1$ so $\Phi_p(x)$ is $P^2k'+1$ but $\Phi_p(x)=1+p+p^2+...+p^{p-1} \equiv p+1 \pmod{p^2}$ so exist $q$ such that $q\mid \Phi_p(x),v_p(q-1)=1$

Pick a prime $q$ such that $q\mid p^p-1$ but $q\nmid p-1$, and $q\not\equiv 1\pmod p^2$. Such a $q$ must exist because \[p^{p-1}+\dots + p+1\equiv p+1\pmod p^2\]Now, suppose $n^p\equiv p \pmod q$ then $n^{p^2}\equiv p^p\equiv 1\pmod q$ so $\text{ord}_q(n)\mid \text{gcd}(p^2,q-1)$ but $p^2\nmid q-1$ so $n^p\equiv 1\pmod q$, contradiction.

This is quite a funny problem. The key is to pick some prime $q \mid \frac{p^p - 1}{p-1}$ but $q \not \equiv 1 \pmod p^2$. Now everything miraculously falls apart as we can write the congruence $$n^{p^2} \equiv p^p \equiv 1 \pmod q,$$hence $p^2 \mid q-1$ or $n^p \equiv 1 \pmod q$. Both cases are impossible, so we're done.

huh Pick a prime $q \mid p^{p-1} + p^{p-2} + \dots + 1 = \frac{p^p - 1}{p-1}$ such that $p^2 \nmid q - 1$, which clearly must exist (else $p^{p-1} + p^{p-2} + \dots + 1 \equiv 1 \pmod{p^2}$, contradiction.) Now if $n^p \equiv p \pmod{p}$ then $n^{p^2} \equiv p^p \equiv 1 \pmod{q}$, but this implies due to orders that either $p \equiv 1 \pmod{q}$ or that $p^2 \mid q -1$, both contradictions - hence we are done.

welp I hope I didn't mess anything up

Take any $q|\frac{p^p-1}{p-1}$ with $q\not\equiv 1\pmod{p^2}$.

Claim: $x^p-p$ is irreducible over $\mathbb{Z}[x]$. Proof: If it factored, it would be into two monic polynomials. Its roots all have magnitude $\sqrt[p]{p}$, so the product of any $k$ of them where $0<k<p$ is not an integer; contradiction from Vieta's. $\blacksquare$ Now go to section 2.3 here. We are done. $\blacksquare$

Let $p$ be a prime number. Prove that there exists a prime number $q$ such that for every integer $n$, the number $n^p-p$ is not divisible by $q$. For $p=2$, just take $q=3$. Ok, so now assume $p \geq 3$. Pick a prime factor $q$ of \[\Phi_p(p)=\frac{p^p-1}{p-1}\]See that $\gcd(\Phi_p(p),p-1)=1$ and hence the $\text{ord}_q(p)=p$. Now recall this key fact about cyclotomic polynomials. Lemma: If a prime number $r \mid \Phi_m(X)$, then $m \mid r-1$ or $r \mid m$. Which gives light to our following claim which is the meat of the problem. Claim: We can pick $q$ such that $\nu_p(q-1)=1$. Proof: See that $p \mid q-1$, by the lemma. And assume for contradiction, that all prime factors of $\Phi_p(p)$ are $1$ modulo $p^2$. Then we have \[p^2 \mid \Phi_p(p)-1=p^{p-1}+\dots+p\]which is a contradiction. $\blacksquare$ Now we claim $q$ is our desired prime which satisfies the hypothesis of the problem. See that since $p \mid q-1$, $n^p$ does not "cover everything" modulo $q$. And assume for contradiction that there exists $n$ such that \[n^p \equiv p \pmod q \implies p^{\frac{q-1}p} \equiv 1 \pmod q \iff p=\text{ord}_q(p) \mid \frac{q-1}p\]which goes against our choice of $q$, as desired.

wowww, this is trivialised by chebotarev noting that the polynomial $p(x)=x^p-p$ is irreducible by eisenstein Edit: oh yea forgot to mention yall @below

Solved with kotmhn and quantum13. Trivial by Chebotarev. $\blacksquare$

Morally correct solution is this my solution is #50, but.... By Eisenstein, noth that $f(x)=x^p-p$ is irreducible polynomial and hence by Anti-Schur's theorem (which is just consequence of Chebotarev's theorem), we are done.

Let $\Phi_{p}(x)$ be the $p$-th cyclotomic polynomial, and let $q$ be a prime such that $q \mid \Phi_{p}(p),$ and $p^{2} \nmid q-1.$ Then, $\text{ord}_{q}(p) = p,$ so $p \mid q-1,$ and thus $q > p.$ Then, $n^{p} \equiv p \pmod q,$ implies $n^{p^{2}} \equiv p^{p} \equiv 1 \pmod q,$ so $p^{2} \mid q-1$ by orders.