How to prove it true for any n ?

**simplependulum** · April 7th 2010, 10:13 PM

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 .

**NonCommAlg** · April 8th 2010, 03:00 AM

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.

**tonio** · April 8th 2010, 03:23 AM

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

**Opalg** · April 8th 2010, 05:05 AM

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.

**tonio** · April 8th 2010, 05:36 AM

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.

.

**tonio** · April 8th 2010, 05:40 AM

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

**chiph588@** · April 8th 2010, 11:38 AM

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}$ .

**NonCommAlg** · April 9th 2010, 02:49 AM

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!

Thread: How to prove it true for any n ?

LinkBack

Thread Tools

Display

How to prove it true for any n ?

Similar Math Help Forum Discussions

prove whether the set property is true, false, or sometimes true and sometimes false?

Prove whether the set property is always true, always false, or sometimes true or fal

h^(n)= ∑ (k=0 to n) n!/k!(n-k)!f^(n-k) * g^(k)(x) : Prove that the following is true

True or False. Prove if true show counter example if false.

Help prove the following is true.

Search Tags