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

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

3. Hello, ruprotein!

Is there a typo in #1?

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!

4. 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)$

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

-Dan

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