Gcd

Printable View

December 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
December 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
January 1st 2007, 05:04 AM
Soroban

Hello, ruprotein!

Is there a typo in #1?

Quote:

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

(a) Find $g$ .

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

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

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

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

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

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

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

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

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

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

Check

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

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

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

. . . . . . $= \;2$ . . . check!
January 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,
$242=1\cdot 142+100$
$142=1\cdot 100+42$
$100=2\cdot 42+ 16$
$42=2\cdot 16+10$
$16=1\cdot 10+6$
$10=1\cdot 6+4$
$6=1\cdot 4+2$
$4=2\cdot 2+0$
Ah! The gcd is 2.

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

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

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

Quote:

Originally Posted by ThePerfectHacker

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

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

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

Now, we can use the identity for continued fractions,
$p_kq_{k-1}-q_kp_{k-1}=(-1)^{k-1}=-1$
Thus,
$121(27)-71(46)=1$
Multiply by 2 (gcd) to make numbers appear,
$242(27)-142(46)=2$
Thus,
$242(27)+142(-46)=2$
Thus,
$242x+142y=2$
For $(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
January 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.