Доказателство на теоремата на Ойлер: (m,n)=1 ⇒ φ(nm) = φ(m).φ(n)
Теорема на Ойлер:
Ако m и n са взаиммно прости, то: φ(nm) = φ(m).φ(n)
Доказателство:
Разглеждаме множеството {mx+y} , където x = 1, … , n-1 и y = 1, … , m-1.
Множеството mx пробягва пълната система от остатъци на n, понеже m и n са взаимно прости.
Сред тази пълна система по модул nφ(n) ще бъдат взаимно прости с n.
Пълна система от остатъци по модул n се получава и в {mx+y} при непроменящо се y.
При променящо се y и непроменящо се x сред {mx+y} ще има φ(m) остатъци, взаимно прости с m.
В долната таблица е демонстрирано доказателството при m=6 и n=7.
В нея са разположени числата от вида 6.x+y при x = 1, … , (7-1) и y = 1, … , (6-1).
Във всеки ред се получава пълна система от остатъци по (mod 6).
Тези, които са взаимно прости с 6 са очветени в червено.
Във всеки ред се получава пълна система от остатъци по (mod 7).
Тези, които не са взаимно проси със 7 са очветени в синьо.