Почему среди чисел 1a, 2a, ... (p - 1)a нет двух разных чисел, сравнимых по модулю p, если a не кратно p?

Для ответа на вопрос о том, почему среди чисел 1a, 2a, ... (p - 1)a нет двух разных чисел, сравнимых по модулю p, если a не кратно p, можно использовать теорему Эйлера. Согласно этой теореме, если a и p взаимно просты, то a возводимое в степень (p-1) по модулю p равно 1. То есть, a^(p-1) = 1 (mod p). Если существуют два числа i и j, такие что i < j и ia = ja (mod p), то (j-i)*a = 0 (mod p). Так как a не кратно p, то j-i должно быть кратно p, что противоречит тому, что i < j ≤ p-1. Следовательно, нет двух разных чисел, сравнимых по модулю p, если a не кратно p1.



Для доказательства этого утверждения можно использовать малую теорему Ферма, которая гласит, что если p - простое число, а a - целое число, не кратное p, то a^(p-1) ≡ 1 (mod p).Предположим, что существуют два разных числа i и j, такие что i < j и ia ≡ ja (mod p). Тогда (j-i)*a ≡ 0 (mod p), что означает, что p делит (j-i)a. Так как p - простое число, то p должно делить (j-i) или a. Но так как i < j, то (j-i) < p, что означает, что p не может делить (j-i). Также, так как a не кратно p, то p не может делить a. Получается, что p не может делить (j-i) или a, что противоречит тому, что p делит (j-i)a. Следовательно, предположение о том, что существуют два разных числа i и j, такие что i < j и ia ≡ ja (mod p), неверно.Таким образом, можно заключить, что среди чисел 1a, 2a, ..., (p-1)*a нет двух разных чисел, сравнимых по модулю p, если a не кратно p.

Для простого p?

От обратного - пусть есть такие числа na ma, n не равно m.
Тогда na - ma кратно p
(n - m)a = lp

Правая часть - не ноль и кратна простому p
Правая часть при разложении на простые множители будет содержать p, левая - нет, получили противоречие с основной теоремой арифметики

Предположим, что они есть, то есть числа ka и na равны по модулю р при некоторых k, n <=p-1. Тогда ka≡na (mod p) или a(k-n)≡0 (mod p). Тк а и р взаимно просты, то k-n≡0 (mod p) или k≡n (mod p), что неверно. Противоречие

Это попросту неверно в такой формулировке. Пусть a=2, p=4, а не кратно p
1a=2≡2(mod 4)
2a=4≡0(mod 4)
3a=6≡2≡1a(mod 4)
(добавьте простоту p)