Results 1 to 8 of 8

Math Help - How to prove it true for any n ?

  1. #1
    Super Member
    Joined
    Jan 2009
    Posts
    715

    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 .
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    Quote Originally Posted by simplependulum View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by simplependulum View Post
    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
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by tonio View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by Opalg View Post
    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.
    .
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by NonCommAlg View Post
    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
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by simplependulum View Post
    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} .
    Last edited by chiph588@; April 8th 2010 at 07:47 PM.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    Quote Originally Posted by tonio View Post
    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!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 7
    Last Post: October 5th 2011, 01:45 PM
  2. Replies: 1
    Last Post: October 4th 2011, 03:19 AM
  3. Replies: 2
    Last Post: September 16th 2010, 06:34 AM
  4. True or False. Prove if true show counter example if false.
    Posted in the Differential Geometry Forum
    Replies: 0
    Last Post: March 2nd 2010, 11:54 AM
  5. Help prove the following is true.
    Posted in the Geometry Forum
    Replies: 6
    Last Post: November 19th 2008, 06:40 PM

Search Tags


/mathhelpforum @mathhelpforum