Processing math: 54%

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


a,b,m және k2 натурал сандары берілген. ЕҮОБ(φm(n),[kan+b])=1 болатындай шексіз көп натурал n сандарының табылатынын дәлелдеңіз. (Бұл жерде φ1(n)=φ(n) — Эйлер функциясы, ол 1-ден n-ге дейін неше сан n санымен өзара жай екенін көрсетеді, ал барлық i1 үшін φi+1(n)=φ(φi(n)). [x] арқылы x санынан аспайтын ең үлкен бүтін сан белгіленген.) ( Сатылханов К. )
посмотреть в олимпиаде

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

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

Берем большие простые вида p=at1. Тогда n=p(p+1)k1a подходят. (Теорему Дирихле нельзя использовать в Казахстане.)

  4
1 года 4 месяца назад #

Мы найдем бесконечно много n, таких что kan+b является простым числом, скажем p, и n удовлетворяет условию νp(n)=1 а p — наибольший простой делитель числа n. Обратите внимание, что тогда p для любого положительного целого числа m, так что таким образом мы обеспечим взаимную простоту.

У нас есть \lfloor \sqrt[k] {an+b} \rfloor=p \iff p^k \leq an+b <(p+1)^k. Мы ищем n=pM для некоторого (M, p)=1 с простыми делителями меньше p, такого что M>p^{k-1}, что гарантирует выполнение нижней оценки. Для верхней границы нам понадобится an+b<(p+1)^k \iff p+\frac{b} {aM}<\frac{(p+1)^k}{aM}. Так как M>p^{k-1}, то для достаточно больших p имеем b<aM, поэтому нам нужен \frac{(p+1)^k}{aM} \geq p+1 , следовательно, выбора aM=(p+1)^{k-1} будет достаточно, так как это также будет означать, что наибольший простой делитель числа n равен p. Осталось найти бесконечно много простых чисел p таких, что a \mid p+1, что возможно Дирихле. Следовательно, эта конструкция работает, и мы закончили.