`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

You must be logged in to post a comment.