# Gcd

• Dec 31st 2006, 09:06 PM
ruprotein
Gcd
Let a = 242, b = 142. Let g be the gretest common divisor of a and b, Find g, and find integers m,n such that g = m*a+n*n

I found g = 2

So 2 = 242m + n^2

how can i find m and n?

Also what is the fastest way to prove the following:

if a,b are integers, g is a natural number, and g is the GCD of a and b, then there exist integrs m,n suc that g = m*a+n*b?

Everywhere i check online they are giving me longgggg solutions,but what if this question was given on an exam that is an hour long, i had it on my midterm this semester
• Dec 31st 2006, 10:59 PM
CaptainBlack
Quote:

Originally Posted by ruprotein
Also what is the fastest way to prove the following:

if a,b are integers, g is a natural number, and g is the GCD of a and b, then there exist integrs m,n suc that g = m*a+n*b?

Everywhere i check online they are giving me longgggg solutions,but what if this question was given on an exam that is an hour long, i had it on my midterm this semester

I don't know if this is the fastest method of proving it, but:

A way to prove it is by considering the Extended Euclidean Algorithm, which
gives a decreasing sequence of positive integers g_k:

g_k=m_k*a+n_k*b

(with m_k and n_k integers) each of which is divisible by the gcd(a,b), and
if g_k>g another step can always be performed, so the sequence eventualy
reaches a k such that g_k=g.

A not very clear explanation of the EEA can be found here.

RonL
• Jan 1st 2007, 05:04 AM
Soroban
Hello, ruprotein!

Is there a typo in #1?

Quote:

Let $\displaystyle a = 242,\;b = 142.$
Let $\displaystyle g$ be the greatest common divisor of $\displaystyle a$ and $\displaystyle b$.

(a) Find $\displaystyle g$.

(b) Find integers $\displaystyle m,\,n$ such that: .$\displaystyle g \:= \:m\cdot a + n\cdot \bf{b}$
typo?

(a) You already found that: $\displaystyle GCD(242,\,142)\:=\:2$

(b) We want integers $\displaystyle m$ and $\displaystyle n$ so that: .$\displaystyle 242m + 142n \:=\:2$ [1]

We have: .$\displaystyle 121m - 1 \:=\:71n$

. . Then: .$\displaystyle 121m \:\equiv \:1 \pmod{71}$

Multiply both sides by $\displaystyle 27\!:\;\;1350m \:\equiv \:27\!\!\pmod{71}\quad\Rightarrow\quad m \:\equiv \:27\!\!\pmod{71}$

. . Hence: .$\displaystyle \boxed{m \:=\:27 + 71a}$ for any integer $\displaystyle a.$

Substitute into [1]: .$\displaystyle 242(27 + 71a) + 142n \:=\:2$

. . Hence: .$\displaystyle \boxed{n \:=\:\text{-}46 - 121a}$ for any integer $\displaystyle a.$

~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Check

Substitute into [1]: .$\displaystyle 242m + 142n \:=\:2$

We have: .$\displaystyle 242(27 + 71a) + 142(-46 - 121a)$

. . . . . .$\displaystyle = \:6534 + 17182 a - 6532 - 17182a$

. . . . . .$\displaystyle = \;2$ . . . check!

• Jan 1st 2007, 09:34 AM
ThePerfectHacker
Quote:

Originally Posted by ruprotein
Let a = 242, b = 142. Let g be the gretest common divisor of a and b, Find g, and find integers m,n such that g = m*a+n*n

Euclidean algorithm,
$\displaystyle 242=1\cdot 142+100$
$\displaystyle 142=1\cdot 100+42$
$\displaystyle 100=2\cdot 42+ 16$
$\displaystyle 42=2\cdot 16+10$
$\displaystyle 16=1\cdot 10+6$
$\displaystyle 10=1\cdot 6+4$
$\displaystyle 6=1\cdot 4+2$
$\displaystyle 4=2\cdot 2+0$
Ah! The gcd is 2.

That means that,
$\displaystyle 242/142=[1;1,2,2,1,1,1,2]$

Thus,
$\displaystyle p_0=a_0$
$\displaystyle p_1=a_1a_0+1$
$\displaystyle p_k=a_kp_{k-1}+p_{k-2}, k\geq 2$
Using this relations we find,
$\displaystyle p_0=1$
$\displaystyle p_1=1\cdot 1 +1=2$
$\displaystyle p_2=2\cdot 2+1=5$
$\displaystyle p_3=2\cdot 5+2=12$
$\displaystyle p_4=1\cdot 12+5=17$
$\displaystyle p_5=1\cdot 17+12=29$
$\displaystyle p_6=1\cdot 29+17=46$
$\displaystyle p_7=2\cdot 46+29=121$
Und,
$\displaystyle q_0=1$
$\displaystyle q_1=a_1$
$\displaystyle q_k=a_kq_{k-1}+q_{k-2}, k\geq 2$
Using these relations we find,
$\displaystyle q_0=1$
$\displaystyle q_1=1$
$\displaystyle q_2=2\cdot 1+1=3$
$\displaystyle q_3=2\cdot 3+1=7$
$\displaystyle q_4=1\cdot 7+3=10$
$\displaystyle q_5=1\cdot 10+7=17$
$\displaystyle q_6=1\cdot 17+10=27$
$\displaystyle q_7=2\cdot 27+17=54+17=71$

Now, we can use the identity for continued fractions,
$\displaystyle p_kq_{k-1}-q_kp_{k-1}=(-1)^{k-1}=-1$
Thus,
$\displaystyle 121(27)-71(46)=1$
Multiply by 2 (gcd) to make numbers appear,
$\displaystyle 242(27)-142(46)=2$
Thus,
$\displaystyle 242(27)+142(-46)=2$
Thus,
$\displaystyle 242x+142y=2$
For $\displaystyle (x,y)=(27,-46)$
• Jan 1st 2007, 10:18 AM
topsquark
Quote:

Originally Posted by ThePerfectHacker
Euclidean algorithm,
$\displaystyle 242=1\cdot 142+100$
$\displaystyle 142=1\cdot 100+42$
$\displaystyle 100=2\cdot 42+ 16$
$\displaystyle 42=2\cdot 16+10$
$\displaystyle 16=1\cdot 10+6$
$\displaystyle 10=1\cdot 6+4$
$\displaystyle 6=1\cdot 4+2$
$\displaystyle 4=2\cdot 2+0$
Ah! The gcd is 2.

That means that,
$\displaystyle 242/142=[1;1,2,2,1,1,1,2]$

Thus,
$\displaystyle p_0=a_0$
$\displaystyle p_1=a_1a_0+1$
$\displaystyle p_k=a_kp_{k-1}+p_{k-2}, k\geq 2$
Using this relations we find,
$\displaystyle p_0=1$
$\displaystyle p_1=1\cdot 1 +1=2$
$\displaystyle p_2=2\cdot 2+1=5$
$\displaystyle p_3=2\cdot 5+2=12$
$\displaystyle p_4=1\cdot 12+5=17$
$\displaystyle p_5=1\cdot 17+12=29$
$\displaystyle p_6=1\cdot 29+17=46$
$\displaystyle p_7=2\cdot 46+29=121$
Und,
$\displaystyle q_0=1$
$\displaystyle q_1=a_1$
$\displaystyle q_k=a_kq_{k-1}+q_{k-2}, k\geq 2$
Using these relations we find,
$\displaystyle q_0=1$
$\displaystyle q_1=1$
$\displaystyle q_2=2\cdot 1+1=3$
$\displaystyle q_3=2\cdot 3+1=7$
$\displaystyle q_4=1\cdot 7+3=10$
$\displaystyle q_5=1\cdot 10+7=17$
$\displaystyle q_6=1\cdot 17+10=27$
$\displaystyle q_7=2\cdot 27+17=54+17=71$

Now, we can use the identity for continued fractions,
$\displaystyle p_kq_{k-1}-q_kp_{k-1}=(-1)^{k-1}=-1$
Thus,
$\displaystyle 121(27)-71(46)=1$
Multiply by 2 (gcd) to make numbers appear,
$\displaystyle 242(27)-142(46)=2$
Thus,
$\displaystyle 242(27)+142(-46)=2$
Thus,
$\displaystyle 242x+142y=2$
For $\displaystyle (x,y)=(27,-46)$

Is it just me or is it every time he does his continued fractions approach it seems like the blackest of magics? :p

-Dan
• Jan 1st 2007, 10:54 AM
ThePerfectHacker
Quote:

Originally Posted by topsquark
Is it just me or is it every time he does his continued fractions approach it seems like the blackest of magics? :p

This is like the third time somebody make a comment to me like that. The joke that they were saying that each time I respond it always involves continued fractions. I really have no idea why most of my posts involve continued fractions. It is funny I know.