2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

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

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

 
 
 
 Re: Свойство взаимно простых чисел
Сообщение22.06.2013, 18:43 
И на какую последовательность намекает $a^m-1$?

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

 
 
 
 Re: Свойство взаимно простых чисел
Сообщение22.06.2013, 19:35 
Аватара пользователя
lena7
lena7 в сообщении #739456 писал(а):
Это почти теорема Эйлера (обобщение малой теоремы Ферма). Она доказывается в одну строчку в рамках теории групп. Я даже считаю, что полезней ознакомится с основами теории групп, чем доказывать эту теорему элементарными школьными методами.

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

-- 22.06.2013, 18:39 --

iifat
iifat в сообщении #739454 писал(а):
И на какую последовательность намекает $a^m-1$?

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

 
 
 
 Re: Свойство взаимно простых чисел
Сообщение23.06.2013, 07:44 
Аватара пользователя
Решение оказалось простым. Действительно, "за деревьями я не увидел леса". :oops:

При делении чисел вида $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,$ чтобы получить требуемое утверждение.

 
 
 [ Сообщений: 5 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group