доказать Малую теорему Ферма

[Marizza]

Помогите пожалуйчта доказать Малую теорему Ферма. Пожалуйста!!! Я сама пыталась доказывать через индукцию, но это док-во получилось не корректным (по словам препода). Он мне дал намёк на док-во через поле Zp по теореме Лагранжа.Но у меня не получается. Может вы мне поможите? Пожалуйста...

[Руст]

Это очень просто. Покажем, что обратимые элементы (точнее вычеты взаимно простые с n) кольца Z/nZ образуют группу. Для этого берём произвольный взаимно простой с n элемент x и расмотрим последовательные степени по модулю n. Они все взаимно просты с n, следовательно среди n таких найдутся два равных. Отсюда получается, что некоторая степень равна 1 по модулю n, т.е. для каждого х имеется обратный. Другие аксиомы теории групп относительно вычетов тривиальны. Отсюда следует (теорема Лежандра), что:
$ x^{\phi(n)}=1(mod \ n)$.