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 $\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!

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,
$\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)$

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

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