# Thread: How to prove it true for any n ?

1. ## How to prove it true for any n ?

I have a number theory question and i don't know what to begin with .

Show that for each prime $p$, there exists a prime $q$ such that
$n^p - p$ is NOT divisible by $q$ for any positive integer $n$.

Thanks a lot .

2. Originally Posted by simplependulum
I have a number theory question and i don't know what to begin with .

Show that for each prime $p$, there exists a prime $q$ such that
$n^p - p$ is NOT divisible by $q$ for any positive integer $n$.

Thanks a lot .
i'm not sure, i think there's a result which says if $f \in \mathbb{Z}[x]$ with $\deg f \geq 2$ has a root modulo every prime, then $f$ is reducible in $\mathbb{Z}[x].$ if this is true, then your problem will be just a trivial

application of it. it's quite late now and my brain is not functioning anymore. so maybe someone can find a proof or a reference for that.

3. Originally Posted by simplependulum
I have a number theory question and i don't know what to begin with .

Show that for each prime $p$, there exists a prime $q$ such that
$n^p - p$ is NOT divisible by $q$ for any positive integer $n$.

Thanks a lot .

Talking modulo p, we get $n^p-p=n\!\!\!\pmod p\,,\,\,\forall n\in\mathbb{N}$ . As n runs over the naturals it will always hit, of course, on multiples of q...

For example, when $n=q\Longrightarrow q^p-p=q\!\!\!\pmod p$ and we're done: the claim is false as stated, imo.

Tonio

4. Originally Posted by tonio
Talking modulo p, we get $n^p-p=n\!\!\!\pmod p\,,\,\,\forall n\in\mathbb{N}$ . As n runs over the naturals it will always hit, of course, on multiples of q...

For example, when $n=q\Longrightarrow q^p-p=q\!\!\!\pmod p$ and we're done: the claim is false as stated, imo.
But $q^p-p\equiv q\!\!\!\pmod p$ does not imply that $q^p-p$ is a multiple of q.

The result is true for p=3, with q=7. If n is a multiple of 7 then clearly $n^3-3$ is not divisible by 7. If n is not a multiple of 7 then $n^3 \equiv \pm1\!\!\!\pmod7$, and so $n^3-3 \not\equiv 0\!\!\!\pmod7$. The same argument will work for any prime p such that q = 2p+1 is also prime. But I do not see how to extend it to the general case. Maybe that requires some more abstract argument such as NonCommAlg's.

5. Originally Posted by Opalg
But $q^p-p\equiv q\!\!\!\pmod p$ does not imply that $q^p-p$ is a multiple of q.

Indeed: confused 'divisibility by q" with "divisibility by q mod p"

Tonio

The result is true for p=3, with q=7. If n is a multiple of 7 then clearly $n^3-3$ is not divisible by 7. If n is not a multiple of 7 then $n^3 \equiv \pm1\!\!\!\pmod7$, and so $n^3-3 \not\equiv 0\!\!\!\pmod7$. The same argument will work for any prime p such that q = 2p+1 is also prime. But I do not see how to extend it to the general case. Maybe that requires some more abstract argument such as NonCommAlg's.
.

6. Originally Posted by NonCommAlg
i'm not sure, i think there's a result which says if $f \in \mathbb{Z}[x]$ with $\deg f \geq 2$ has a root modulo every prime, then $f$ is reducible in $\mathbb{Z}[x].$ if this is true, then your problem will be just a trivial

application of it. it's quite late now and my brain is not functioning anymore. so maybe someone can find a proof or a reference for that.

Alas, the theorem seems to be false: http://tinyurl.com/yl25nob , and btw theorem 1 there appears to be really fascinating.

Tonio

7. Originally Posted by simplependulum
I have a number theory question and i don't know what to begin with .

Show that for each prime $p$, there exists a prime $q$ such that
$n^p - p$ is NOT divisible by $q$ for any positive integer $n$.

Thanks a lot .
Your question is asking if $x^p\equiv p\bmod{q}$ is solvable i.e. is $p$ a $p^{th}$ power residue modulo $q$?

Theorem: Let $q$ be a prime. If $(a,q)=1$, then $a$ is an $n^{th}$ power residue modulo $q \iff a^{\frac{\phi(q)}{d}}\equiv1\bmod{q}$, where $d=(n,\phi(q))$. Ask if you'd like to see why this is true.

Let $a=n=p$. If $d=1$, then we look at $p^{\phi(q)}\bmod{q}$. But $p^{\phi(q)}\equiv1\bmod{q}$ by flt. Thus we want $d\neq1\implies d=p\implies p\mid q-1\implies q=kp+1$.

Dirichlet tells us there's an infinite amount of primes of this form.

So we now know $q\equiv1\bmod{p}$, but this isn't enough.

We need $p^{(q-1)/p}\not\equiv1\bmod{q}$... and now I'm stuck.

Edit: Opalg's post supports this: $p=3,\; q=7$ and $q\equiv1\bmod{p}$.

8. Originally Posted by tonio
Alas, the theorem seems to be false: JSTOR: An Error Occurred Setting Your User Cookie , and btw theorem 1 there appears to be really fascinating.

Tonio
that theorem actually proves my claim because the polynomial $f(x)=x^p-p$ is irreducible (by Eisenstein's criterion) and its degree is a prime number. so, by that theorem it cannot be reducible

(and therefore cannot have a root) modulo every prime number.

today i talked to a friend of mine, who is a number theorist, about the result i mentioned and he confirmed my guess. he said that even a stronger result can be proved:

if $f(x) \in \mathbb{Z}[x]$ has a root modulo every prime, then $f(x)$ has a "linear factor" (as an element of $\mathbb{Z}[x]$). this is a very interesting result!