Question

Докажите, что 7^120-1 делится на 143

Answer 1

143=11*13. Значит если число делится и на 11 и на 13 то оно делится и на 143, так как 11 и 13 простые. Нам нужно доказать что $7^{120}\equiv1 mod 143$

Но если мы докажем что $7^{120}\equiv1 mod 11$и $7^{120}\equiv1 mod 13$, то мы докажем что 7^120-1 делится на 143.

Используем малую теорему ферма и получим что: $7^{10}\equiv1 mod 11$.

Возведем обе части в натуральную степень 12 получим что 

$(7^{10})^{12}\equiv1^{12} mod 11$. То есть $7^{120}\equiv1 mod 11$. Таким же образом доказывается для числа 13. 

----------

Если что не понятно пишите