Processing math: 100%

Республиканская олимпиада по математике, 2017 год, 9 класс


Натуральное число a и простое p таковы, что НОД(a,p!)=1. Докажите, что a(p1)!1 делится на p!. ( Ануарбеков Т. )
посмотреть в олимпиаде

Комментарий/решение:

Комментарии от администратора Комментарии от администратора №1.     Решение. По малой теореме Ферма ap11(modp), следовательно a(p1)!1(modp). Пусть (p1)!=qα11qα22qαkk — каноническое разложение числа (p1)!. Так как p1q11 и (qα11,q11)=1, то (p1)!q1α11(q11)=φ(q1α1).
По теореме Эйлера aφ(qα11)1(modqα11), следовательно a(p1)!1(modqα11). Аналогично для каждого i=2,3,,k получаем, что a(p1)!1(modqαii). Значит, a(p1)!1pqα11qα22qαkk=p!, что и требовалось доказать.

  5
2 года 6 месяца назад #

Факт: пусть n=pα11pα22pαkk, pP,(a,p)=1, и λ(n)=[ϕ(pα11),ϕ(pα22),ϕ(pαkk)]. Тогда aλ(n)1modn (1)

Из факта (1) выходит, что достаточно доказать λ(p!)(p1)! Для этого докажем, что Vq(λ(p!))Vq((p1)!),qP.Пусть p!=pα11pα22pαkk - каноническое разложение числа p!. Тогда Vq(λ(p!))=max[Vq(ϕ(pα11)),Vq(ϕ(pα22)),Vq(ϕ(pαkk)]=Vq(ϕ(pαjj))Но ϕ(pαjj)=(pj1)(pαj1j) и очевидно pαj1j(pj1)(p1)!Vq(λ(p!))Vq((p1)!), ч.т.д.

  6
2 года 6 месяца назад #

Абзал аби мощь

пред. Правка 2   5
1 года 8 месяца назад #