Question

prove that gcd(a,m) = 1 and gcd(b,m) = 1 if and only if gcd(ab,m) = 1

Just If gcd(ab,m) = 1, then gcd(a,m) = 1 and gcd(b,m) = 1 only

Answer 1

attempt: We are going to provide a proof by contradiction.
Suppose gcd(a,m) isn't equal to one. Then there exist an integer e >1 such that a = xe and m = ye for some integers x and y. Moreover if gcd(b,m) isn't equal to one, then there exist an integer f >1 such that b = gf and m = hf for some integers g and h. The product of ab = xegf will either have a factor of e > 1, which is m = ye, or a factor of f >1. which is m =hf in common with m. Therefore, gcd(ab,m) can't be 1.

Answer 2

@wio

Answer 3

sounds like a job for bezout right? i think it is called bezout

Answer 4

except that's not in my book for some reason ._.

Answer 5

you know for the proofs on gcd(2n+1,9n+4) = 1 would it be ok to use Euclid's Algorithim? I think it's easier .

Answer 6

bezout is just another name for
\(gcd(a,b)=1\iff ax+by=1\) for some \(x,y\)

Answer 7

strange...I've read about it online but my book doesn't have it :/

Answer 8

that gives you one direction right away
if there exists \(x,y\) with \(ax+my=1\) and \(x',y'\) with \(bx'+my'=1\) then
\[(ax+my)(bx'+my')=1\] expand on the left and get something with \[ab\xi +m\zeta=1\]

Answer 9

Contrapositive
If \(\gcd(a,m)\neq 1\) or \(\gcd(b,m)\neq 1\) then there is some integer \(k>1\), where \(k|m\) and \(k|a\) or \(k|b\). That means that \(k|ab\), and we already know \(k|m\).
This means \(\gcd(ab,m)\geq k\gt 1\) so \(\gcd(ab,m)\neq 1\).

Answer 10

going the other way without bezout will be a challenge
not really sure it can be done

Answer 11

so k can be any number that' s bigger than one
since k divides a and k divides b ... the end result will be bigger numbers so the gcd(ab,m) can't be equal to 1

Answer 12

Well, the idea is that \(\gcd(a,m)=k\neq 1\) or \(\gcd(b,m)=k\neq 1\).