dati due numeri a e b, sono coprimi se
$$ \boxed{MCD(a,b)=1} $$
in questo caso si parla di numeri estremamente grandi, maggiori di $10^{99}$ quindi la scomposizione in numeri primi non è fattibile
per risolvere questo problema si utilizza il teorema di Euclide, che recita
<aside> 👉 “Dati due numeri naturali $a,b$ , entrambi maggiori di 1 con $a>b$ (se $b$ è un divisore esatto $a$) $\rarr$( $b$ è ovviamente il massimo comun divisore tra i due numeri) altrimenti (detto $r$ il resto della divisione tra $a$ e $b$ ) $\rarr$ ( il MCD tra a e b è uguale al MCD tra b e r )”
</aside>
in poche parole il teorema di euclide ci permette di definire questo:
$$ MCD(a,b)=d\\ a = b * q1 + r1\\ b = r1 * q2 + r2 \\ r1 = r2 * q3 + r3 \\ ...
$$
si continua in questo modo fino a quando non si ottiene un resto $r_k$ pari a zero
prendendo poi il resto $r_{k-1}$ si ottiene proprio il numero $d$ che si stava cercando all’inizio
ad esempio
$$ MCD(1180,482)\\ 1180/482 = 2 \text { con resto r1 = 216}\\ 482/216=2 \text { con resto r2 = 50}\\ 216/50=4 \text { con resto r3 = 16}\\ 50/16=3 \text { con resto r4 = 2}\\ 16/2=8 \text { con resto r5 = 0}\\ MCD(1180,482) = 2 $$
$$ ax + by = d $$
importante ricordare che
<aside> 👉 se a e b sono coprimi tra loro, allora $MCD(a,b)=1$
</aside>
quindi secondo il teorema poco fa citato:
$$ ax+by=d\\ \Darr\\ ax\equiv \text{1 mod n} $$
con il teorema di euclide è possibile trovare l’MCD tra i due numeri
e poi si utilizzano i quozienti usati fino al passo k-1
$$ x=\begin{cases} x0=1\\ x1=0\\ x_j = -q_{j-1}*x_{j-1}+x_{j-2} \\ \end{cases}\\
y=\begin{cases} y0=1\\ y1=0\\ y_j = -q_{j-1}*y_{j-1}+y_{j-2} \\ \end{cases} \\ $$