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

Printable View

- Feb 17th 2014, 08:35 PMoregongirlRelatively 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...

- Feb 17th 2014, 10:24 PMromsekRe: Relatively Prime proof
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}$$