Suppose that n and m are relatively prime Prove that n and m

Suppose that n and m are relatively prime.

Prove that n and m + jn are relatively prime for any integer j. Then, explain why this statement implies that if n and m are relatively prime and m\' = m mod n, then n and m\' are relatively prime.

Solution

Assume, n and m+jn are not relatively prime

So, gcd(n,m+jn)=g>1

n=kg

m+jn=k\'g

m+jkg=k\'g

m=(k\'-jk)g

Hence, m and n are multiples of g

So, gcd(n,m)>=g

which is a contradiction

Hence,n,m+jn are relatively prime

Now let,

m\'=m mod n

ie

m\'-m=0 mod n

So, m\'-m=jn

m\'=m+jn

Hence, m\' and n are relatively prime as:n,m+jn are relatively prime as we proved above