# Math Help - Relatively Prime proof

1. ## 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...

2. ## Re: Relatively Prime proof

Originally Posted by oregongirl
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}$$