§ 5. ПЕРВООБРАЗНЫЕ КОРНИ И ИНДЕКСЫ

Порядок числа и класса вычетов по модулю.

Пусть а — число, взаимно простое с т. Порядком числа а по модулю называется наименьшее целое положительное число d такое, что Если , то b имеет тот же порядок по модулю , что и а. Таким образом, все элементы класса вычетов имеют порядок d; число d называется порядком класса вычетов и обозначается через

ПРЕДЛОЖЕНИЕ 5.1. Если то числа попарно несравнимы по модулю .

Доказательство. Если , где , то , что противоречит условию, так как

ПРЕДЛОЖЕНИЕ 5.2. Пусть и — любое целое неотрицательное число. Сравнение выполняется тогда и только тогда, когда делится на

Доказательство. Сначала покажем, что из следует, что делится на d. По теореме о делении с остатком, для и d существуют натуральные числа q и такие, что

Покажем, что Ввиду (1) и условия

Так как, по условию, если то сравнение возможно лишь при . Следовательно, делится на d. Теперь предположим, что делится на для некоторого k. Тогда

ПРЕДЛОЖЕНИЕ 5.3. Если то делится на

Доказательство. В силу предложения 5.2 из и условия следует, что делится на d.

ПРЕДЛОЖЕНИЕ 5.4. Пусть . Сравнение имеет место тогда и только тогда, когда

Доказательство. Если

то

и поэтому в силу предложения 5.2 делится на d, т. е.

Обратно: из (3) следует (2) и (1).

ПРЕДЛОЖЕНИЕ 5.5. Пусть а, b — числа, взаимно простые с т. Если числа взаимно простые, то

Доказательство. Пусть . Докажем, что f делится на . Так как , то . Из в силу предложения 5.2 следует, что делится на d. Так как, по условию, то f делится на d. Также находим, что f делится на е. Следовательно, f делится на .

С другой стороны, . Согласно предложению 5.2, отсюда следует, что делится на Следовательно, .

ПРЕДЛОЖЕНИЕ 5.6. Если и d — натуральный делитель числа , то .

Доказательство. Пусть . По условию, . Согласно предложению 5.2, отсюда следует, что делится для некоторого натурального числа k. Следовательно, . Отсюда следует, что делится на . Поэтому

ПРЕДЛОЖЕНИЕ 5.7. Если , то

Доказательство. Пусть . Из условия следует, что

Следовательно, число делится на f. С другой стороны, . Согласно предложению 5.2, отсюда следует, что делится на . Поэтому делится на Так как то f делится на следовательно,

ПРЕДЛОЖЕНИЕ 5.8. Если то

Это предложение непосредственно следует из предыдущего.