Relatively Prime Integers

`a` and `b` are said relatively prime if `GCD(a,b)=1`.

Euler’s Totient function, `\phi(n)`, counts the number of positive integers less than `n` that are are relatively prime to `n`.

For example, numbers relatively prime to 15 are `{1,2,4,7,8,11,13,14}`, so `\phi(15)=8`.

 1,  2,  3,  4,  5,  6,  7 8,  9, 10, 11, 12, 13, 14

There is always an interesting symmetry to these lists, that is, if `a` is in the list, then `n-a` is in the list.

Take `a<n` and `GCD(a,n)=1`.

Now lets suppose that `n` and `n-a` are not relatively prime, so `GCD(n-a,n)=d>1`.

This means that `d|n` so there exists a `k` where `n=dk`. Similarly, `n-a=dj` for some `j`.

Then `a=n-dj=dk-dj=d(k-j)`, so that `d|a`, contradicting our hypotheses, `GCD(a,n)=1`.

So `d` must me `1`.

This may also be shown using the fact that `a` and `n` are relatively prime, if and only if there exist integers `x` and `y` such that `ax+ny=1`.(ref)

So far, I lack an simpler argument that if `a` is relatively prime to `n` and `a<n` then `n-a` is also.

Leave a Reply