Results 1 to 2 of 2
Like Tree1Thanks
  • 1 Post By romsek

Math Help - Relatively Prime proof

  1. #1
    Newbie
    Joined
    Feb 2014
    From
    Oregon
    Posts
    4

    Relatively Prime proof

    I am asked to prove that 2^100+1 and 2^100+3 are relatively prime using a=qb+r, gcd(a,b)=gcd(b,r). I'm not entirely sure how these two integers fit into the format a=qb+r...
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2013
    From
    California
    Posts
    2,201
    Thanks
    848

    Re: Relatively Prime proof

    Quote Originally Posted by oregongirl View Post
    I am asked to prove that 2^100+1 and 2^100+3 are relatively prime using a=qb+r, gcd(a,b)=gcd(b,r). I'm not entirely sure how these two integers fit into the format a=qb+r...
    well I'll take a stab at it

    $$\begin{align*}\\ &q=1 \\ \\ &b=2^{100}+1 \\ \\ &r=2 \\ \\ &\mbox{then }a=2^{100}+3\end{align*}$$

    $$gcd(2^{100}+3,2^{100}+1)=gcd(a,b)=gcd(b,r)=gcd(2 ^{100}+1,2)$$

    $$\mbox{2 only has 2 divisors, 1 and 2.}$$

    $$\mbox{Pretty clearly }\left(2^{100}+1\right) (mod 2) = 1\mbox{ so }gcd(2^{100}+1,2)=1\mbox{ thus }gcd(2^{100}+3,2^{100}+1)=1 \\ \\ \mbox{ and thus }2^{100}+3\mbox{ and }2^{100}+1\mbox{ are relatively prime}$$
    Thanks from oregongirl
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 0
    Last Post: January 9th 2013, 07:35 PM
  2. Relatively Prime Proof
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: November 20th 2010, 12:18 AM
  3. Prime # Proof
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: April 21st 2010, 06:06 PM
  4. Prime Proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: October 23rd 2008, 12:30 AM
  5. Prime proof
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: September 5th 2008, 08:03 PM

Search Tags


/mathhelpforum @mathhelpforum