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