Hitta en heltalslösning

Börja med att lösa ekvationen $35x+21y=1$. 

Du tar alltså fram hjälpekvationen, det följer sedan att:

om $(x_0,y_0)$ löser $35x+21y=1$ så är den allmänna lösningen:

$(cx_0 \mp nb, cy_0 \pm na)$ och som tidigare är $(x_0,y_0)$ lösningar till hjälpekvationen $ax+by=1$.

blir det inte så att 
gcd (35,21) = 7

$$\begin{gathered} ( 35x+21y=1 ) / 7 =\hspace{0.17em}5x + 3yy =\hspace{0.17em}9 \\ ---- \\ Eukilds algortim:\hspace{0.17em} \\ 35=\hspace{0.17em}21*1 + 14 \\ 21=\hspace{0.17em}14*2+\mathbf{7} \\ 14=7*2+0 \\ --- \\ 5= 3*1 +2 \\ 3=2*1+1 \\ 2=1*2 + 0 \\ ---- \\ 1=3-(2*1) \\ 2=\hspace{0.17em}5- (3*1) \\ --- \\ 1=3-(5- (3*1)*1) \\ \hspace{0.17em}=\hspace{0.17em}3*2 - 5*1 \\ Sen multiplicerar jag 2 *9 och 1*9 \\ jag får (9, -18) \end{gathered}$$

Men jag får fel.. :(

nära, men det borde väl bli $(-9,18)$.

Så att en lösning är:

$(-9)35+21(18)=-315+378=63$ vilket stämmer bra. 

Man behöver egentligen inte köra igenom euklides.

5x+3y=1 kan man identifiera direkt har lösningen x=-1 och y=2, för att då fås -5+6=1, sedan kan vi som jag visade i mitt första inlägg nämligen att använda hjälpekvationen för att ta fram den allmänna lösningen. :)