Thread: 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 $\displaystyle p$, there exists a prime $\displaystyle q$ such that
$\displaystyle n^p - p $ is NOT divisible by $\displaystyle q$ for any positive integer $\displaystyle n$.

Thanks a lot .

Originally Posted by simplependulum

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


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

Thanks a lot .

i'm not sure, i think there's a result which says if $\displaystyle f \in \mathbb{Z}[x]$ with $\displaystyle \deg f \geq 2$ has a root modulo every prime, then $\displaystyle f$ is reducible in $\displaystyle \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.

Originally Posted by simplependulum

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


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

Thanks a lot .

Talking modulo p, we get $\displaystyle 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 $\displaystyle n=q\Longrightarrow q^p-p=q\!\!\!\pmod p$ and we're done: the claim is false as stated, imo.

Tonio

Originally Posted by tonio

Talking modulo p, we get $\displaystyle 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 $\displaystyle n=q\Longrightarrow q^p-p=q\!\!\!\pmod p$ and we're done: the claim is false as stated, imo.

But $\displaystyle q^p-p\equiv q\!\!\!\pmod p$ does not imply that $\displaystyle 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 $\displaystyle n^3-3$ is not divisible by 7. If n is not a multiple of 7 then $\displaystyle n^3 \equiv \pm1\!\!\!\pmod7 $, and so $\displaystyle 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.

Originally Posted by Opalg

But $\displaystyle q^p-p\equiv q\!\!\!\pmod p$ does not imply that $\displaystyle 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 $\displaystyle n^3-3$ is not divisible by 7. If n is not a multiple of 7 then $\displaystyle n^3 \equiv \pm1\!\!\!\pmod7 $, and so $\displaystyle 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.

.

Originally Posted by NonCommAlg

i'm not sure, i think there's a result which says if $\displaystyle f \in \mathbb{Z}[x]$ with $\displaystyle \deg f \geq 2$ has a root modulo every prime, then $\displaystyle f$ is reducible in $\displaystyle \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

Originally Posted by simplependulum

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


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

Thanks a lot .

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

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

Let $\displaystyle a=n=p $. If $\displaystyle d=1 $, then we look at $\displaystyle p^{\phi(q)}\bmod{q} $. But $\displaystyle p^{\phi(q)}\equiv1\bmod{q} $ by flt. Thus we want $\displaystyle 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 $\displaystyle q\equiv1\bmod{p} $, but this isn't enough.

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

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

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 $\displaystyle 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 $\displaystyle f(x) \in \mathbb{Z}[x]$ has a root modulo every prime, then $\displaystyle f(x)$ has a "linear factor" (as an element of $\displaystyle \mathbb{Z}[x]$). this is a very interesting result!