Grestest Common Divisor {GCD}

2014-02-24 12:50 pm

Assume that m,n,and p are integers and gcd(mn,p)=1. Show that gcd(m,p)=1.
Clearly indicate reasons for each step in your proof.

What I did:
K=gcd(mn,p)
mn=K*a
p =K*b

But what is the next step?

Thanks

回答 (1)

Tony

2014-02-24 4:37 pm

✔ 最佳答案

THEOREM: If a and b are nonzero integers, then their gcd is
a linear combination of a and b,
that is there exist integer numbers s and t such that
sa + tb = gcd(a, b).

so, gcd(mn,p)=1 can be expressed as
a(mn) + b(p) = 1 (a, b are integers)

notice that a(mn) + b(p) = 1 can be written as
an(m) + b(p) = 1 (an is an integer)

by theorem, gcd(m,p) = 1

to find gcd, Euclidean Algorithm is a method.

2014-02-24 08:57:11 補充：
https://onedrive.live.com/redir?resid=A3980BFF0EA16013!187&authkey=!ADOKdxYr9Ff3w60&v=3&ithint=photo%2c.png

you are right. gcd(300^40,2^57) = 2^57

參考: myself, myself

👍 0 👎 0