Processing math: 11%

Областная олимпиада по математике, 2022 год, 9 класс


Пусть p — простое число, дающее остаток 1 при делении на 4. Найти все такие натуральные числа a, b и c, которые одновременно удовлетворяют условиям
   a) наибольший общий делитель чисел a, b и c равен 1;
   b) ab не делится на p;
   c) 1a+1b+1cp=4p. ( Абдыкулов А. )
посмотреть в олимпиаде

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

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

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

(a,b,c)=1 (a,b), (b,c), (a,c)=1

я так же подумал и совершил ошибку на области)

пример: (4,6,11)=1

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

АДМИН, сделай уже функцию удаления комментариев!

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

a=dx,b=dy,(x,y)=1

Үшінші берілген теңдікті abcp-ға көбейтейікте, d-ға бөліп жіберейік: dycp+dxcp+d^2xy=4d^2xyc \rightarrow ycp+xcp+dxy=4dxyc\rightarrow dxy(4c-1)=cp(x+y)

Ал енді қарасақ, xy p мен x+y бөлінбейді, сонда c \vdots xy, ал c, (4c-1)-ге бөлінбейді (c=1 болса, 3dxy=p(x+y) ге келеміз, сонда 3 \vdots p, ондай мүмкін емес) және (c,d)=1, солай xy \vdots c. Сонымен xy=c екенін түсіндік, онда соны қолдансақ: d(4xy-1)=p(x+y)

4xy-1 \vdots p екені анық, 4xy-1 \equiv 3(mod 4), сол үшін \exists q\equiv 3(mod 4),4xy-1 \vdots q.. Және де x+y \vdots q, онда x \equiv -y(mod q) және (2y)^2+1 \vdots q (ал бұл Жерар теоремасы бойынша мүмкін емес).

Жауабы: Ондай сандар жоқ.

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

В какой книге вы узнали о теореме Жерара?

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

Мне на уроке наш выпускник лицея объяснил, он по сути объяснил про две теоремы p=3k+2,p=4k+3, потом мне в комментариях подсказали что это Теорема Жерара

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

Мне тоже стало интересно - что это еще за теорема Жерара? Я впервые услышал о таком и не понимал, неужели эту задачу можно решить только с помощью столь малоизвестной теоремы? Это что, заговор составителей из била против остальных школ? Они специально делают такие задачи и такие малоизвестные теоремы преподают только в своих школах? Я был бы готов в это поверить учитывая то, насколько для этой системы школ важен успех на олимпиадах. Но, к счастью, всё оказалось намного проще.

В гугле ноль результатов по запросу теорема Жерара и на русском, и на английском, его не оказалось ни в задачнике Прасолова, ни даже в Алфутовой. Его нет даже в справочных материалов в книге с задачами и решениями областного этапа, ни даже в книге по АТМО и МОШП. Потом я решил искать не по названию теоремы, а по его утверждению. Оказалось это самая обыкновенная, наверное, даже самая базовая задача с использованием МТФ. Она гласит - "Если x^2+1 делится на нечетное простое p, то p=4k+1" (см. https://www.problems.ru/view_problem_details_new.php?id=60752, советую ознакомиться). То есть здесь, в этом решении, вышло бы, что q=4k+1 хотя это не так.

Эта задача есть в сборнике олимпиадных задач Горбачева (13.116) в разделе про теорему Ферма и Эйлера, в Алфутовой (4.142), в Прасолове есть более обобщенная версия (31.2) - вторая задача сразу после непосредственно доказательства МТФ.

Если же говорить о задаче, как до этого можно было додуматься, то, как мне кажется, трудно было бы заранее не зная об этом факте, МТФ, додуматься, что q\:|\:4y^2+1 ведет к противоречию. Видимо составитель предполагал, что школьник знаком с МТФ и ему довелось, в качестве упражнения в книге по которой он это изучал, доказать "Теорему Жерара" так, что он даже если и может позабыл, но сможет быстро восстановить все это в памяти и я с этим полностью согласен.

Вот такое у меня вышло расследование. Человек который в комментариях к мопсичку написал, что это теорема Жерара - заблуждается.

Мопсичку спасибо за решение, иначе я бы наверное никогда бы не догадался до идеи о том, что число вида 4k+3 должно делиться на какое-то простое вида 4n+3, а до МТФ в конце тем более (я безуспешно решал эту задачу последние несколько дней). Надеюсь мой комментарий сделал более ясным все решение и я помогу кому-то с подготовкой к области.

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

конспирологический бред вы конечно вначале подумали, pokpokben (чел который мне ответил) сам из НИШа)

я вообще вначале думал что это лемма что если a^2+b^2 делится на p=4k+3 то они по отдельности делятся на p, а мне потом он подсказал что это Теорема Жерара

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

кстати, как не странно автор задачи выпускник моего лицея, 10 или 15 лет тому назад (но я никогда не слышал о нем и он нам никогда не преподавал)

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

На самом деле это довольно-таки известная вещь, которая обязательно проходится, если вы изучали квадратичные вычеты. Теорему Жерара также говорят "теорема Жирара", наверное, из-за этого ничего и не нашли

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

Да, действительно, я немного ошибся. Спасибо что подсказали

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

Мопсичек, керемет! Қазақша жазуды бастапсын ғой)

Ал, sovetov.m-ның бір әріпте қате жіберіп, сол үшін конспирология жасап, бұл туралы ізденгені - қызық көрініс

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

қатені мен жасадым ғой

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

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

Қиындатып жібердім деп ойламайсыз ба?

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

Эх бала)

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

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

Если кого-то немного сбивает с толку, что (a,\,b,\,c)=1 на самом деле не обязательно влечет (a,\,b)=1,\,(b,\,c)=1,\,(a,\,c)=1 то это можно представить себе так. Представьте каждое число как мультимножество его простых делителей. Мультимножество это то же самое множество, но у которого элементы могут повторяться. К примеру, 6=\{2,\,3\},\,100=\{2,2,5,5\}, 13=\{13\}, а единица это пустое множество. Тогда у нас выйдет, что, например, a\,|\,b \Leftrightarrow A\subset B или (a,\,b)=1\Leftrightarrow A\cap B=\varnothing и т.д. Множества же хороши тем, что их можно представить в виде диаграмм Эйлера-Венна. Конкретно здесь (a,\,b,\,c)=1 можно представить как диаграмму из 3 множеств A, B, C которые не имеют общего пересечения. Понятно, что если все три сразу где-то не пересекаются, то это не значит, что каждая пара множеств не пересекается.

Я нашел это в книге Modern Olympiad Number Theory от Aditya Khurmi, пункт Looking at Numbers as Multisets.

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

қызық екен!

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

решаю без теормеы Жерара я понял что если (a,b,c)=1 то это не означает (a,b)=1,(b,c)=1,(c,a)=1 пример (6,10,15)=1

заметим что если ab не делится на p то a,b не делитя на p тогда это выражение можно переписать в виде bcp+acp=ab(4c-1) тогда 4c-1=p,4c-1=cp,4c-1=cp(a+b) три случая разберем третий тогда a,b=1 подставляя 1+1+\dfrac {1}{cp}>\dfrac{4}{4k+1} где k\geq 1 этоо вариант неправилен тогда разберем 2 вариант заметим что 4c-1=cp где p=4k+1 тогда 4c-1=cp правое делится на c левое нет если c>1 пусть тогда c=1 тогда p=3 а по условии p \equiv 1 \pmod {4} разбираем первый вариант тогда bc+ca=ab где 4c-1=4k+1\Rightarrow4c=4k+2противоречие по мод 4 противоречие