Республиканская олимпиада по математике, 2017 год, 9 класс
Комментарий/решение:
Комментарии от администратора Комментарии от администратора №1. Решение. По малой теореме Ферма ap−1≡1(modp), следовательно a(p−1)!≡1(modp). Пусть (p−1)!=qα11qα22…qαkk — каноническое разложение числа (p−1)!. Так как p−1≥q1−1 и (qα11,q1−1)=1, то (p−1)!⋮q1α1−1(q1−1)=φ(q1α1).
По теореме Эйлера aφ(qα11)≡1(modqα11), следовательно a(p−1)!≡1(modqα11). Аналогично для каждого i=2,3,…,k получаем, что a(p−1)!≡1(modqαii). Значит, a(p−1)!−1⋮p⋅qα11qα22…qαkk=p!, что и требовалось доказать.
Факт: пусть n=pα11pα22…pαkk, p∈P,(a,p)=1, и λ(n)=[ϕ(pα11),ϕ(pα22),ϕ(pαkk)]. Тогда aλ(n)≡1modn (1)
Из факта (1) выходит, что достаточно доказать λ(p!)∣(p−1)! Для этого докажем, что Vq(λ(p!))≤Vq((p−1)!),∀q∈P.Пусть p!=pα11pα22…pαkk - каноническое разложение числа p!. Тогда Vq(λ(p!))=max[Vq(ϕ(pα11)),Vq(ϕ(pα22)),…Vq(ϕ(pαkk)]=Vq(ϕ(pαjj))Но ϕ(pαjj)=(pj−1)(pαj−1j) и очевидно pαj−1j(pj−1)∣(p−1)!→Vq(λ(p!))≤Vq((p−1)!), ч.т.д.
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.