Friday, January 3, 2020

elementary number theory - Prove for all $n in N$, $gcd(2n+1,9n+4)=1$

Question: Prove for all $n \in N$, $\gcd(2n+1,9n+4)=1$



Attempt: I want to use Euclid's Algorithm because it seemed to be easier than what my book was doing which was manually finding the linear combination.




Euclid's Algorithm states that we let $a,b \in N $. By applying the Division Algorithm repeatedly...then $\gcd(a,b) = r_j$ will be the last non-zero remainder. By the Well Ordering Principle, there is a smallest element of the set of natural numbers less than or equal to $r_j$.



I have used long division, but since I can't get it to show up here, I will type what I've done.



Starting at $\gcd(2n+1,9n+4)$,



$\frac{2n+1}{9n+4}$



I can multiply $2n+1$ four times and I would have a remainder of $n$ because $(9n+4)-(8n+4) = 9n+4-8n-4=n$




so we have $4 \cdot (2n+1)+n$ if I apply Euclid's Algorithm.



For $\gcd(2n+1, n)$,



$\frac{2n+1}{n}$



I can multiply $n$ 2 times and I will have only 1 as the remainder because $(2n+1)-(2n+0) = 2n+1-2n+0=1$



Therefore, we have $2 \cdot (n) +1$




and $\gcd(n,1)$ which is $1$



Since the end result is $1, \gcd(2n+1,9n+4)=1$



I followed an example from this link



http://cms.math.ca/crux/v33/n5/public_page274-276.pdf



Am I doing this correctly?

No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...