Why does this work? "If a & b are relatively prime, any integer can be written as ma + nb for m, n ∈ ℤ."

Question

I don't understand how that theorem is true. For example,

"If a & b are relatively prime", 3 and 4 are relatively prime.

"any integer", let's choose 5.

There's no m and n (∈ ℤ) combination for 3 and 4 that gives 5. What am I thinking wrong here?

Answer 1

actually its corect - try to remember that for any two integers a and b there are c, d $\in Z$ so that ac + bd = gcd(a,b) there for in our case ac+bd = 1 and thats why we can choose for any integer z : m = zc , n = zd and we get ma+nb = z(ac+bd) = z*1 = z as wanted

Answer 2

First of all for $3$ and $4$ to generate $5$, you notice that $4-3 =1$ thus $5(4)-5(3)=5.$

In general if $m$ and $n$ are relatively prime you can find integers $a$ and $b$ such that $$am+bn=1.$$

for an arbitrary integer $k$, we multiply $$am+bn=1$$ by $k$ and get $$ (ka)m+(kb)n=k$$

for example since $7$ and $5$ are relatively prime we get $$3(5)-2(7)=1.$$ Let $k=37$ and we get $$37\times 3(5)- 37\times 2(7)= 37.$$

Answer 3

It's called Bezout's lemma.

For any $n,m $ where $\gcd (n,m)=1$ and $n>m $ you can find by the division algorithm a $q,r $ so that:

$n=qm+r $ where $r <n $.

Notice, any factors that $r $ and $m $ have in common, $n $ does too. But $n $ and $m $ have no factors in common, so $r $ and $m $ are relatively prime.

If $r =1$ we are done: $n-qm=1$.

And if there are $a,b $ so that $am+br=1$ then $am+b (n-qm)=1$ and $m (a-bq)+bn=1$ and we are done.

So there are solutions, if there are solutions to $am+br=1$.

But we can do the same thing for $m, r$.

Let $m=pr+s $ then $\gcd (m,s)=1$ and $s <r $. And there exist $a,b $ so that $am+br=1$ if there exist $c,d $ so that $cr+ds=1$.

We can keep doing this and each time the remainder gets smaller. The remainder will never be zero because it will always be relatively prime to the quotient. If the remainder is larger than zero we can repeat this. But we can't repeat it forever because every repition the remainder gets smaller.

So eventually the remainder will be $1$ and these equations are possible.

Example: to solve for $11$ and $7$. And try to find $m,n $ so $11m+7n=1$

$11=7+4$. If we can solve $7a+4b=1$ we are done. Because we will have $7a+(11-7)b=7 (a-b)+11b=1$

$7=4+3$ if we can solve $4c+3d=1$ we are done. Because we will have $4c+(7-4)d=4 (c-d) +7d=1$.

$4=3+1$ so $1=4*1+3*(-1)=1$. $c=1; d=1$.

so $4 (c-d)+7d=4 (1-(-1))+7*(-1)=4*2-7=1$. So $a=-1;b=2$.

So $7(a-b)+11b=7 (-1-2)+11 (2)=11*2-3*7=2$ and $m=2$ and $n=3$.

And so to get $11p+7q=z $ just let $p=nz=2z $ and $q=mz=3z$.

Example to get $11p+7q=37$ we do $11*74-7*111=37 (11*2-7*3)=37*1=37$.

Now it might seem $p=74$ and $q=-111$ aren't a nice answer because they are so far apart.

Well we can find closer answers.

$11 (74- 7)+7 (-111+11)=11*74+7*(-111)-77+77=11*74-7*111=37$

So $11 (67)+7*(-100) =37$

And we can do it again. $11*60-7*89=11*53-7*78=11*46-7*67=11*39-7*56=11*32-7*45=11*25-7*34=11*18-7*23=11*11-7*12=11*4-7=37$