# 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.