Results 1 to 6 of 6

Math Help - Two Not So Quick Questions

  1. #1
    Super Member Aryth's Avatar
    Joined
    Feb 2007
    From
    USA
    Posts
    652
    Thanks
    2
    Awards
    1

    Two Not So Quick Questions

    I've been wondering if there are proofs for these two questions... Searching has given me nothing. These aren't new results so they SHOULD be out there, but I can't find them.

    1. Let p and q be distinct primes. Prove that, for any a \in \mathbb{Z}

    a^{pq} \equiv a^p + a^q (mod \ pq)

    2. Let a < m be two positive integers. Prove that a and m are relatively prime if and only if there is some power of a which is an inverse of a modulo m.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    Quote Originally Posted by Aryth View Post
    I've been wondering if there are proofs for these two questions... Searching has given me nothing. These aren't new results so they SHOULD be out there, but I can't find them.

    1. Let p and q be distinct primes. Prove that, for any a \in \mathbb{Z}

    a^{pq} \equiv a^p + a^q (mod \ pq)
    this is false! check the question again!
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    Quote Originally Posted by Aryth View Post

    2. Let a < m be two positive integers. Prove that a and m are relatively prime if and only if there is some power of a which is an inverse of a modulo m.
    the "if" part: if a^k \equiv a^{-1} \mod m, then a^{k+1} \equiv 1 \mod m. now it's clear that a,m cannot have any common divisor greater than 1.

    for the "only if" part use this fact that if \gcd(a,m)=1, then a^{\varphi (m)} \equiv 1 \mod m and thus a^{\varphi(m)-1} \equiv a^{-1} \mod m.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member Aryth's Avatar
    Joined
    Feb 2007
    From
    USA
    Posts
    652
    Thanks
    2
    Awards
    1
    Quote Originally Posted by NonCommAlg View Post
    this is false! check the question again!
    You're right... I missed a part:

    a^{pq} + a \equiv a^p + a^q (mod \ pq)
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    Quote Originally Posted by Aryth View Post
    You're right... I missed a part:

    a^{pq} + a \equiv a^p + a^q (mod \ pq)
    since x-y \mid x^n - y^n, for any positive integer n, we have q \mid a^q - a \mid a^{pq} - a^p and p \mid a^p - a \mid a^{pq}-a^q. thus q \mid a^{pq} - a^p and p \mid a^{pq} - a^q. thus:

    q \mid a^{pq}-a^p - (a^q - a) and p \mid a^{pq}-a^q - (a^p -a). but a^{pq}-a^p - (a^q - a)= a^{pq}-a^q - (a^p -a). thus: pq \mid a^{pq}-a^p - a^q + a, and we're done.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member Aryth's Avatar
    Joined
    Feb 2007
    From
    USA
    Posts
    652
    Thanks
    2
    Awards
    1
    Thanks for the help. I really appreciate it.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Two quick questions.
    Posted in the Algebra Forum
    Replies: 6
    Last Post: September 22nd 2009, 04:06 PM
  2. two quick questions
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: December 8th 2008, 04:19 PM
  3. Some quick questions
    Posted in the Algebra Forum
    Replies: 12
    Last Post: November 1st 2008, 10:54 AM
  4. PLEASE HELP! 2 quick questions! thanks!
    Posted in the Algebra Forum
    Replies: 1
    Last Post: September 19th 2008, 04:47 AM
  5. 3 Quick Questions
    Posted in the Trigonometry Forum
    Replies: 5
    Last Post: May 8th 2007, 08:12 PM

Search Tags


/mathhelpforum @mathhelpforum