Loading [MathJax]/jax/output/SVG/jax.js

Республиканская олимпиада по математике, 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(n) для любого положительного целого числа m, так что таким образом мы обеспечим взаимную простоту.

У нас есть kan+b=ppkan+b<(p+1)k. Мы ищем n=pM для некоторого (M,p)=1 с простыми делителями меньше p, такого что M>pk1, что гарантирует выполнение нижней оценки. Для верхней границы нам понадобится an+b<(p+1)kp+baM<(p+1)kaM. Так как M>pk1, то для достаточно больших p имеем b<aM, поэтому нам нужен (p+1)kaMp+1, следовательно, выбора aM=(p+1)k1 будет достаточно, так как это также будет означать, что наибольший простой делитель числа n равен p. Осталось найти бесконечно много простых чисел p таких, что ap+1, что возможно Дирихле. Следовательно, эта конструкция работает, и мы закончили.