Results 1 to 3 of 3
Like Tree1Thanks
  • 1 Post By Idea

Thread: If p and q are distinct odd primes, prove 2pq+1≡2p+q(modpq)

  1. #1
    Newbie JLin7's Avatar
    Joined
    Oct 2016
    From
    Cambridge, Massachusetts
    Posts
    5

    Lightbulb If p and q are distinct odd primes, prove 2pq+1≡2p+q(modpq)

    Please help me for this question.. I dont have any idea how to solve it...
    Last edited by JLin7; Oct 28th 2016 at 05:47 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Jun 2013
    From
    Lebanon
    Posts
    742
    Thanks
    341

    Re: If p and q are distinct odd primes, prove 2pq+1≡2p+q(modpq)

    2^p\equiv 2 (mod p)
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2016
    From
    Roma
    Posts
    3

    Re: If p and q are distinct odd primes, prove 2pq+1≡2p+q(modpq)

    We will use Euler's Theorem, so let us first find $\phi(pq)$.

    $$\phi(pq) = pq \left(1-\frac{1}{p}\right) \left( 1- \frac{1}{q} \right) = (p-1)(q-1) = (pq+1)-(p+q).$$

    Now, since $\gcd{(2,pq)} = 1$ ($p$ and $q$ are odd), by Euler's theorem,
    $$2^{(pq+1)-(p+q)} \equiv 1 \mod{pq}.$$

    Multiplying by $2^{p+q}$ gives the desired result.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Pairwise distinct primes
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: Aug 30th 2013, 12:13 PM
  2. (p^m)(q^n) Distinct Odd Primes
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Apr 11th 2012, 02:40 PM
  3. Replies: 10
    Last Post: Dec 19th 2011, 10:34 AM
  4. Prove that |G| ≡ h mod 16.
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: Mar 15th 2011, 12:13 PM
  5. Twins of primes with one distinct prime factor
    Posted in the Differential Geometry Forum
    Replies: 0
    Last Post: Nov 8th 2010, 10:53 AM

/mathhelpforum @mathhelpforum