Свойство взаимно простых чисел

[angor6]

Задача, с решением которой возникла проблема, помещена в начале учебника по алгебре и аналитической геометрии, а не по теории чисел. В прошлом году решил эту задачу, но теперь не могу вспомнить, как я это сделал: "Доказать, что если числа $a$ и $b$ взаимно просты, то существует натуральное $m$, для которого $a^m-1$ делится на $b$". Может быть, кто-нибудь предложит своё решение?

Возможно, следует рассмотреть некоторую последовательность чисел, дающих разные остатки при делении на $b$. Среди $b+1$ этих чисел обязательно найдутся такие, которые дают одинаковые остатки. Их разность делится на $b.$ Эту разность нужно представить как произведение множителей, одним из которых является число вида $a^m-1,$ а другие множители не кратны $b.$ Как-то сложно получается...

Указанной задаче предшествуют три теоремы: о делении с остатком, о свойстве НОД двух чисел, о свойстве произведения двух взаимно простых чисел.

[iifat]

И на какую последовательность намекает $a^m-1$?

[lena7]

Это почти теорема Эйлера (обобщение малой теоремы Ферма). Она доказывается в одну строчку в рамках теории групп. Я даже считаю, что полезней ознакомится с основами теории групп, чем доказывать эту теорему элементарными школьными методами.

[angor6]

lena7

lena7 в сообщении #739456 писал(а):

Это почти теорема Эйлера (обобщение малой теоремы Ферма). Она доказывается в одну строчку в рамках теории групп. Я даже считаю, что полезней ознакомится с основами теории групп, чем доказывать эту теорему элементарными школьными методами.

Тем не менее, меня интересует именно доказательство этого утверждения "школьными методами".

-- 22.06.2013, 18:39 --

iifat

iifat в сообщении #739454 писал(а):

И на какую последовательность намекает $a^m-1$?

$a-1,~a^2-1,~a^3-1,~...$

[angor6]

Решение оказалось простым. Действительно, "за деревьями я не увидел леса".

При делении чисел вида $a^n$ на число $b$ возможны остатки, равные $1,~2,~3,~...,~b-1,$ всего $b-1$ остатков. Построив последовательность $a-1,~a^2-1,~a^3-1,~...,~a^b-1,$ получим два числа, которые при делении на $b$ дают одинаковые остатки. Пусть это будут числа $a^p,~a^q~(p<q).$ Число $a^q-a^p=a^p(a^{q-p}-1)$ при делении на $b$ даёт остаток, равный нулю, то есть делится на $b.$ Но $a^p$ не делится на $b,$ поэтому число $a^{q-p}-1$ делится на $b.$ Можно положить $q-p=m,$ чтобы получить требуемое утверждение.