11-я Балканская математическая олимпиада среди юниоров
Шумен, Болгария, 2007 год
Комментарий/решение:
Решение: По Малой теореме Ферма 3p−3 делится на p. Тогда число 7p+3p−4 при делении на p дает остаток −1.Любое простое число при делении на 4 дает остаток 1, либо 3. Так как p− простое число, то необходимо рассмотреть два случая:
Случай №1. p=4k+3⇒7p+3p−4=7(4k+3)+34k+3−4=28k+34k+3+17≡−1(modp)⇒(28k+34k+3+17)2k+1≡(−1)2k+1=−1(modp)
С другой стороны, число 7p+3p−4 является полным квадратом, то есть 7p+3p−4=x2,x∈Z. Тогда имеем противоречие: −1=(−1)2k+1≡(28k+34k+3+17)2k+1=(x2)2k+1=x4k+2=xp−1≡1(modp)
Случай №2. p=4k+1⇒7p+3p−4=7(4k+1)+34k+1−4=28k+3+34k+1=4⋅7k+(34k+1+1)+2≡2(mod4) Но это противоречит условию задачи, так как квадрат целого числа не может давать остаток 2 при делении на 4.
Решение:
Как пример выше, мы знаем что если к начальному примеру прибавить 1, то оно будет делиться на p.
i) Если прибавить 1, то справа будет a2+1 которое тоже будет делиться на p.
ii) Используя mod 4, получаем что p=4k+3 (сразу исключаем пример когда p-четное когда сравниваем по mod 4).
iii) Так как a2+1 делится на p, то соответсвенно оно делится на 4k+3.
Но если так подумать..
Это невозможно, ибо по Лемме(1) a и 1 делится на p, но 1 не может делиться на p.
(1) Лемма:
Если какие ни-будь a2+b2 делится на p где p вида 4k+3, то a и b делятся на p (p-простое)
Доказательство:
Допустим что это не так.И (a;b,p)=1.
a2 оставляет −b2 (mod p)
соответсвенно a4k+2 оставляет −b4k+2 (mod p)
но по Малой Теореме Ферма a4k+2,b4k+2 оставляют 1 по модулю p
Противоречие. Значит a,b делится на p.
Решение: Докажем от противного. Допустим что число 7p+3^p-4 является точным квадратом для какого то натурального числа n . Тогда рассмотрев по модулю 2 понимаем что n^2 делиться на 4 откуда и число 7p+3^p-4 делиться на 4. Значит рассмотрев по модулю 4, понимаем что простое чило p имеет вид 4k+3. Заметим что по Великой Теореме Ферма чило 7p+3^p-3 делиться на p. Откуда и число n^2+1 делиться на p. Но по теореме Жирара 1 должен делиться на p. Противоречие.
Замечание: Мы рассмотрели для всех нечетных p. Но остается случай где p=2 но это тоже невозможно
**По малая теореме Ферма:**
Если p — простое число и a — целое число, не делящееся на p, то выполняется сравнение:
a^{p-1} \equiv 1 \pmod{p}
**Доказательство:**
Рассмотрим множество остатков по модулю p:
S = \{a, 2a, 3a, \dots, (p-1)a\}
Так как a не делится на p, то все элементы S попарно различны по модулю p.
Это означает, что S является перестановкой множества:
\{1, 2, 3, \dots, p-1\}
Следовательно, их произведения сравнимы по модулю p:
(a \cdot 2a \cdot 3a \cdots (p-1)a) \equiv (1 \cdot 2 \cdot 3 \cdots (p-1)) \pmod{p}
Вынесем a^{p-1} за скобки:
a^{p-1} \cdot (1 \cdot 2 \cdot 3 \cdots (p-1)) \equiv (1 \cdot 2 \cdot 3 \cdots (p-1)) \pmod{p}
Так как 1 \cdot 2 \cdot \dots \cdot (p-1) взаимно просто с p, можно сократить:
a^{p-1} \equiv 1 \pmod{p}
Доказана. \square
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.