Results 1 to 8 of 8

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

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

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

  6. #6
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    3
    Quote Originally Posted by NonCommAlg View Post
    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
    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 $\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} $.
    Last edited by chiph588@; Apr 8th 2010 at 06: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 $\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!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 7
    Last Post: Oct 5th 2011, 12:45 PM
  2. Replies: 1
    Last Post: Oct 4th 2011, 02:19 AM
  3. Replies: 2
    Last Post: Sep 16th 2010, 05:34 AM
  4. True or False. Prove if true show counter example if false.
    Posted in the Differential Geometry Forum
    Replies: 0
    Last Post: Mar 2nd 2010, 10:54 AM
  5. Help prove the following is true.
    Posted in the Geometry Forum
    Replies: 6
    Last Post: Nov 19th 2008, 05:40 PM

Search Tags


/mathhelpforum @mathhelpforum