Тема ТЕОРИЯ ЧИСЕЛ

Остатки и сравнения по модулю

Вспоминай формулы по каждой теме
Решай новые задачи каждый день
Вдумчиво разбирай решения
ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!
Подтемы раздела теория чисел
Разделы подтемы Остатки и сравнения по модулю
Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#104744

Пусть P  — нечётное, большее единицы число и P =p p ...p
    1 2  n  — его разложение на простые множители (среди p ,p ,...,p
 1 2    n  могут быть равные). Тогда для произвольного целого числа a  символ Якоби определяется равенством:

(a)  (a)( a) ( a)
P- =  p1 p2 ...pn ,

где ( )
 api — символы Лежандра. По определению считаем ( )
 a1 = 1  для всех a.  Докажите, обобщённый квадратичный закон взаимности: если P,Q  — взаимно простые нечётные числа, то

( )               ( )
 Q- =(−1)(P−1)4(Q−1)⋅ P-
 P                 Q
Показать доказательство

Сначала проверим случай, когда одно из чисел 1.  Пусть P =1.  Тогда ( Q)= 1, (-1)= 1, (− 1)0 = 1.
  1      Q  То есть действительно всё сходится.

Теперь пусть P =p1p2...pn  и Q= q1q2 ...qk.  Из взаимной простоты следует, что pi ⁄= qj.  Мультипликативность символа Якоби следует из определения и мультипликативности символа Лежандра: (a1a2)  (a2)(a1)
  P   =  P  P  .  Тогда

(  )(  )  ∏n (  ) ∏n (  )  ∏n ∏k(   )(  )
 Q-  P-  =    Q- ⋅    pi  =       qj  pi
 P   Q    i=1 pi  i=1 Q    i=1j=1  pi  qj

По квадратичному закону взаимности для простых чисел получаем, что

(Q )( P)      ∑n  ∑k  pi−1 qj−1-
 -P   Q- = (− 1) i=1 j=1 2   2

Значениие степени − 1  зависит от чётности показателя, то есть нам нужно доказать, что

∑n k∑ pi−-1qj −-1≡ P-− 1Q-−-1 (mod 2)
i=1j=1  2    2      2   2

Для нечётных a, b  заметим, что a−21+ b−21≡ ab−21(mod 2)  (можно явно проверить, рассмотрев остатки по модулю 4:  при равных остатках с обеих сторон получится 0,  при различных остатках — 1).  Тогда заметим, что в сумме можно вынести pi2−1  за второй индекс суммирования:

∑n k∑ p − 1q − 1  ∑n p− 1∑k q − 1  ∑n p − 1Q − 1
     -i2---j2--=    i2---  -j2--≡    -i2----2-- (mod 2)
i=1 j=1            i=1     j=1       i=1

из нашего тождества. Теперь общий множитель Q−1
 2  можно тоже вынести:

∑n pi− 1 Q− 1 Q − 1∑n pi− 1  Q− 1P − 1
   --2---2--= --2--   -2---≡ -2----2-- (mod p)
i=1                i=1

снова по тождеству. То есть у нас получилось в точности то, что и требовалось доказать:

(  ) (  )
  Q-  P- = (−1)(P−1)(4Q−1)
  P   Q

Ошибка.
Попробуйте повторить позже

Задача 2#108630

Пусть p  — простое число, а m > 1,x >1,y > 1  — натуральные числа. Оказалось, что

xp+yp-  (x+-y)m
  2   =   2

Докажите, что m = p.

Подсказки к задаче

Подсказка 1

Для начала попробуйте разобрать случай, когда у чисел x и y есть общий простой нечетный делитель.

Подсказка 2

Если у x и y есть общий простой нечётный делительно, то достаточно посмотреть на его степень вхождения в обоих частях нашего равенства. Теперь пусть у x + y есть нечетный простой делитель q. Что тогда можно сказать про степени вхождения q в нашем равенстве (давайте пока считать, что p > 2)?

Подсказка 3

Для этого достаточно выяснить, как вычислить степень вхождения q в x^p + y^p. Что же может нам помочь в этом?

Подсказка 4

Правильно, лемма об уточнении показателя! Применив ее, легко получить, что m может быть только 1. Теперь можно считать, что x + y вообще не имеет нечётных простых делителей. То есть x + y является степенью двойки. Из нашего равенства также будет следовать, что x^p + y^p тоже степень двойки. Попробуйте осознать, что это бывает довольно редко.

Подсказка 5

Не забудьте рассмотреть случай p = 2. Чтоб разобрать этот случай достаточно на самом деле понять, что при m > 2 правая часть точно больше левой.

Показать доказательство

Пока будем считать, что p> 2.  Пусть q  — простой общий делитель чисел x  и y.  Тогда x = qa ⋅x
       1  и y = qb⋅x
       2  (a≤ b).  Теперь посмотрим на степень вхождения q  в нашем равенстве. Мы получаем, что am = ap,  а значит, m =p.

Следовательно, достаточно доказать задачу для        α
(x,y)= 2 ,  где α≥ 0.  Предположим, что x +y  имеет простой множитель q >2.  Тогда x  и y  по отдельности на q  не делятся. Тогда по лемме об уточнении показателя получаем

   p   p
vq(x + y )= vq(x+ y)+vq(p)

поэтому m = 1,  что неверно. Пусть (x,y) =2α,  а значит, x =2α ⋅x
       1  и y =2β ⋅y
       1  (α ≤ β).  Мы разобрали случай, когда у x +y  есть нечётный простой делитель, поэтому можно считать, что α= β  и          k
x1+ y1 = 2.  Следовательно, из нашего равенства мы получаем, что  p   p  s
x1+ y1 = 2,  где s  — какое-то число. Тогда мы знаем, что  p   k    p   s
x1+ (2 − x1)= 2 .  После раскрытия скобок получаем, что степень вхождения двойки справа равна k,  а слева равна s.  Значит, s= k.  Так как p> 1,  то  p    k    p   k
x1 +(2 − x1) > 2,  а значит, x1 = 1,  и аналогично y1 = 1,  то есть x= y.  Тогда из условия сразу следует, что m = p.

Если же p =2,  то мы получаем 2   2   x+ym
x +y = ( 2 ).  Заметим, что      3    2   2
(x +y) > 4(x + y)  в силу того, что x> 1  и y > 1.  А значит, левая часть нашего равенства при m > 2  точно больше правой. То есть m  тоже равно двум.

Ошибка.
Попробуйте повторить позже

Задача 3#108631

Найдите все натуральные a,b,c  и простые p  такие, что 2apb =(p+ 2)c+ 1.

Подсказки к задаче

Подсказка 1

В случае нечетного c правая часть делится на p+3, а тогда оно является степенью двойки или произведением степени двойки и числа p. Предположим, что это степень двойки. Какие числа тогда заведомо являются вычетами или невычетами по модулю p?

Подсказка 2

Верно! -1 является вычетом, а 2 — невычетом. Тогда -2 — невычет. Возможно ли такое?

Подсказка 3

Конечно же, нет! Пусть теперь p+3 - это произведение степени двойки и p. Легко видеть, что p = 3. Можно ли найти теперь степень вхождения 3 в правую часть?

Подсказка 4

Верно! По лемме об уточнении показателя степень вхождения 3 в правую часть равна степени вхождения 3 в c, увеличенной на 1. Следовательно, с не меньше, чем (b-1)-я степень числа 3. При каких a, b, c это возможно?

Подсказка 5

Остается случай четного c. Обозначим степень вхождения 2 в c через n. Заметим, что если в правой части заменить c на n-ю степень 2, то получится делитель правой части. Тогда мы знаем разложение этой правой части с заменой c на n-ю степень 2 на простые множители. Какие выводы напрашиваются?

Подсказка 6

Верно! Мы видим, что при p > 2 можно применять LTE-лемму по модулю 2! Тогда можно получить уравнение на степени вхождения 2, а что из него следует?

Подсказка 7

Точно! Из этого уравнения легко получается, что степень вхождения 2 в показатель 2 по модулю p равна n+1. Тогда p-1 делится на (n+1)-ю степень 2. Кроме того, можно заметить, что степень вхождения p в левую часть с заменой c на n-ю степень двойки четна. Как тогда можно оценить степень вхождения 2 в b из имеющихся условий?

Подсказка 8

Конечно! Степень вхождения 2 в b, увеличенная на 2, не меньше 3 и не больше степени вхождения 2 в p+3. Отсюда получаем, что p-1 не делится на 8. Какое тогда получается уравнение из исходного?

Подсказка 9

Верно! Мы получаем n = 2 и после подстановки легко видеть, что при p > 5 решений нет (одна из частей уравнения точно больше другой). Остается разобраться со случаями p = 3 и p = 5!

Показать ответ и решение

Предположим, что c  нечетное. Тогда правая часть делится на p +3,  откуда p+3 =2k  или p+ 3= 2kpl.

В первом случае получаем, что p ≡5 (mod 8).  Тогда − 1  является квадратичным вычетом по модулю p,  а 2  — не является, откуда − 2  является квадратичным невычетом по модулю p,  но

( c+1)2
2 2   ≡ −2  (mod p)

откуда получаем противоречие.

Во втором случае получаем, что p+ 3  делится на p,  откуда p= 3.  Тогда имеем уравнение c      a b
5 +1= 2 3.  Заметим, что v2(5c+ 1)= 1,  откуда a= 1.  По лемме об уточнении показателя получаем, что

v3(5c+ 1)=v3(6)+ v3(c)= 1+v3(c)

откуда     b−1
c≥ 3  .  То есть  3b−1    b
5    < 2⋅3,  что возможно только при a= b= c= 1  и p =3.

Разберем случай четного c.  Пусть v2(c)=n,  то есть     n
c =2 ⋅m.  Заметим, что      2n
(p+ 2)  + 1  делит      c
(p+ 2) + 1,  откуда

     n
(p+ 2)2  +1= 2k⋅pl

Заметим, что      2n
(p+2)  + 1≡ 2 (mod 4)  при p> 2,  откуда k= 1.  Тогда      2n        b
(p+2)  − 1=2 ⋅(p − 1).  Тогда

       2n
v2((p +2)  − 1)= v2(p+ 1)+v2(p+3)+ v2(n)− 1

С другой стороны

v2(2 ⋅(pl− 1))= v2(p− 1)+ v2(p+ 1)+v2(l)

откуда

v2(p+3)+ n− 1= v2(p− 1)+v2(l)

Заметим, что  2n+1
2    ≡1 (mod p),  а  2n
2  ⁄≡ 1 (mod p),  откуда следует, что v2(ordp2)= n,  то есть p− 1  делится на n+1
2  .  Тогда p ≡1 (mod 4).  Посмотрим на наше равенство по модулю p+ 1.  Имеем         l
2≡ 2⋅(−1),  откуда l  — четное. Тогда из только что полученного равенства на степени вхождения следует, что

v2(p+ 3)≥ 2+ v2(b)≥ 3

То есть число p − 1  не может делиться на 8.  Значит, n+ 1=2,  откуда n= 1.  Тогда имеем уравнение

(p+ 2)2+ 1= 2pl

Заметим, что при p> 5

 l    2       2
2p≥ 2p > (p+ 2) +1

Если p= 3,  то 26=2 ⋅3l  — нет решений.

Если p= 5,  то 50=2 ⋅5l,  откуда l= 2.

Вернемся к исходному уравнению

72m +1 =2a⋅5b

Посмотрев по модулю 4,  получаем a= 1.  Далее 72m + 1= 5t⋅(72+1).  Но по лемме об уточнении показателя

v5(72m +1)= v5(72+ 1)+v5(m )

откуда m ⋅(72+ 1)≥72m+1,  что не может быть правдой. Значит, c= 2m =2,  a= 1,  b= 2,  p= 5.

Ответ:

 (1,1,1,3),  (1,2,2,5)

Ошибка.
Попробуйте повторить позже

Задача 4#118930

Дано простое число p.  Для каждого натурального x ∈{1,2,...,p− 1} рассмотрим выражение x2+ 3x +1.  Оказалось, что ровно 1  из них делится на p.  Найдите все возможные значения p.

Показать ответ и решение

Пусть a2+ 3a+ 1≡ 0,
          p  рассмотрим обратный вычет a−1  (он существует, так как a⁄≡  0
  p  и p -простое число  ) и выражение  −2    −1
a  + 3a  + 1.

 −2   − 1     a2+ 3a+ 1
a  + 3a  +1 ≡p----a2----≡p 0,

но по условию такое число одно, получаем, что     −1    2
a≡p a  ⇒ a − 1 ≡p 0⇒ a ≡1 или a≡ −1.

Пусть a≡p 1,  тогда 1+ 3+ 1≡p 0 ⇒ p= 5,  проведем проверку, что для x∈ {2,3,4} неверно x2+ 3x+ 1 ≡p 0.

  •         2
x =2 ⇒ x +3x+ 1≡5 1
  • x =3 ⇒ x2+3x+ 1≡5 −1
  • x =4 ⇒ x2+3x+ 1≡5 −1

Пусть a≡p − 1,  тогда a2+ 3a+1 =1 − 3+ 1= −1≡p 0,  что невозможно при любом p.

Ответ:

 p =5

Ошибка.
Попробуйте повторить позже

Задача 5#118941

Даны натуральные числа a,  b  и c  такие, что ab+9b+ 81  и bc+ 9c+81  делятся на 101.  Докажите, что тогда и ca+ 9a +81  тоже делится на 101.

Показать доказательство

Так как 101  это простое число, то у всех ненулевых вычетов есть обратный. Тогда ab+9b+ 81 ≡   0⇒ b⁄≡   0,
          101      101  поэтому перейдём к обратному остатку

      −81− 9b
a ≡101 ---b---

Аналогично b+ 9  взаимно просто с 101,  откуда

                                     −81
bc+ 9c +81≡101 0⇒ c(b+9)≡101 − 81 ⇒ c≡101 b+-9

Тогда то, что нам нужно доказать, действительно, верно

ca +9a+ 81≡101 81(81+-9b)− 9⋅81-+81b+ 81 ≡101
              b(b+9)       b

812-+9⋅81b−-9⋅81b−-81b2−-812− 9⋅81b+-81b2+-9⋅81b
                  b(b+9)                   ≡101 0

Ошибка.
Попробуйте повторить позже

Задача 6#118946

Докажите, что для любого простого p> 3  существует бесконечно много натуральных n  таких, что 2n+ 3n +6n − 1  делится на p.

Показать доказательство

По малой теореме Ферма: если a⁄≡  0⇒ ap−1 ≡ 1.
  p         p  Тогда 2n+p−1 ≡ 2n,3n+p−1 ≡ 3n,6n+p−1 ≡ 6n,
       p          p          p  то есть

 n   n   n      n+p−1   n+p− 1  n+p−1
2  +3 + 6 − 1≡p 2    + 3     +6     − 1

значит, надо найти одно n  такое, что 2n+ 3n +6n − 1≡p 0.

Рассмотрим n= −1,  пусть оно и ненатуральное, последующие будут натуральными:

 −1  −1   −1      3+-2+1-
2  + 3  +6  − 1≡p    6   − 1≡p 0

Ошибка.
Попробуйте повторить позже

Задача 7#118947

Пусть p  — простое число, большее 2.  Докажите, что существует такая перестановка (x,x ,...,x   )
  1 2    p−1  чисел (1,2,...,p − 1),  что

x1x2+ x2x3 +...+ xp−2xp−1 ≡2  (mod p)
Показать доказательство

Пусть x = 1 modp.
 i  i  Условие перепишется следующим образом:

                         -1-  -1-       -----1-----
x1x2+ x2x3+ ...+ xp−2xp−1 ≡p 1⋅2 +2 ⋅3 +...+ (p− 2)⋅(p− 1)

Заметим, что

---1-- ≡p--1-− 1,
j(j+1)   j+ 1  j

тогда

-1-+ -1-+ ...+ -----1----- ≡p 1− 1 + 1− 1+ ...+-1--− -1--≡p
1⋅2  2⋅3      (p− 2)⋅(p− 1)      2   2  3      p− 2  p− 1

    1        1
1− p−-1 ≡p 1− −1-≡p 2

Ошибка.
Попробуйте повторить позже

Задача 8#119614

Для каждого натурального n  определим число φ(n),  равное количеству целых чисел m,1 ≤m ≤ n  взаимно простых с n.  Найти φ(1947).

Источники: Росатом - 2025, 11.3 (см. olymp.mephi.ru)

Подсказки к задаче

Подсказка 1

Заметим, что у 1947 в разложении на простые ровно 3 простых делителя. Давайте попробуем решить задачу в общем виде для чисел с 3 простыми делителями в некоторых степенях.

Подсказка 2

В данном случае будет проще посчитать, сколько всего чисел, не взаимно простых с n, и потом вычесть.

Подсказка 3

Как насчёт того, чтобы сначала отдельно посчитать количество чисел, делящихся на первый простой делитель, затем — на второй, третий, после — на первый и второй и так дальше.

Подсказка 4

А как теперь найти количество не взаимно простых, зная результаты вычислений из предыдущей подсказки? Нужно немного манипуляций с формулой включения-исключения.

Показать ответ и решение

Пусть n =pr1⋅pr2 ⋅pr3,
    1   2  3  где p,p ,p
1  2 3  — различные простые числа, r ,r ,r
 1 2 3  — их (натуральные) кратности. Количество чисел, не больших n,  делящихся на p1 :

     r1−1  r2 r3
n1 = p1 ⋅p2 ⋅p3

Количество чисел, не больших n,  делящихся на p :
 2

     r1  r2−1 r3
n2 = p1 ⋅p2  ⋅p3

Количество чисел, не больших n,  делящихся на p3 :

     r1  r2  r3−1
n3 = p1 ⋅p2 ⋅p3

Количество чисел, не больших n,  делящихся на p1⋅p2 :

n = pr1−1⋅pr2−1⋅pr3
 4   1    2    3

Количество чисел, не больших n,  делящихся на p1⋅p3 :

n5 = pr11−1⋅pr22⋅pr33−1

Количество чисел, не больших n,  делящихся на p2⋅p3

n6 = pr11 ⋅pr22−1⋅pr33−1

И наконец, количество чисел, делящихся на p1⋅p2⋅p3 :

n7 = pr11−1 ⋅pr22−1⋅pr33−1

Общее количество чисел, не взаимно простых с n,  по формуле включений-исключений равно

n1+ n2+n3 − n4− n5− n6+n7 =pr11−1⋅pr22−1⋅pr33−1(p1⋅p2+ p1⋅p3+p2⋅p3− p1− p2− p3+ 1)

Тогда

φ(n)= n− n1− n2 − n3+ n4+ n5+n6 − n7 =

= pr1−1⋅pr2−1⋅pr3−1(p ⋅p ⋅p − p ⋅p − p ⋅p − p ⋅p +p + p +p − 1)=
  1     2    3    1  2 3   1  2  1  3   2 3   1   2  3

= pr1−1⋅pr2−1⋅pr3−1(p1− 1)(p2− 1)(p3− 1)
  1     2    3

Таким образом, при n =1947= 3⋅11 ⋅59  имеем

φ(1947)= (3− 1)(11− 1)(59− 1)= 1160
Ответ:

1160

Ошибка.
Попробуйте повторить позже

Задача 9#121044

Пусть a ,a,...,a
 1 2     p−21  — все квадратичные вычеты по модулю p.  Для k= 1,  2,  3,  …, p−1
 2  найдите

σk(a1,a2,...,ap−12 ) (mod p)
Показать ответ и решение

Квадратичными вычетами по модулю p  являются те и только те числа, которые удовлетворяют сравнению a p−21-≡1 (mod p).  Давайте рассмотрим многочлен   p−21-
x    − 1.  Его корни a1,a2,...,ap−21.  Если вспомнить теорему Виета, становится ясно, что σk(a1,a2,...,ap−21) (mod p)  — модуль коэффициента при  p−1
x 2 −k  у рассмотренного многочлена, умноженный на (−1)k.  Все коэффициенты, кроме свободного члена, равны 0,  значит, соответствующие сигмы сравнимы с 0,  а σp−1≡ (−1)p−21-(mod p).
  2

Ответ:

 σ ≡ 0 (mod p)
 k  при k < p−1-
    2  и σ    ≡(−1)p−21(mod p)
  p−21-

Ошибка.
Попробуйте повторить позже

Задача 10#121643

Найдите все пары числел (p,n),  где p− простое, а n− целое и при этом p4+ 211= n2+ 5pn.  В ответе укажите значения n.  Если их несколько, перечислите их в любом порядке через запятую.

Источники: ИТМО-2025, 11.6(см. olymp.itmo.ru)

Подсказки к задаче

Подсказка 1

Хотим использовать малую теорему Ферма (МТФ). Посмотрим на левую часть: по какому модулю удобно рассматривать остаток?

Подсказка 2

Рассматриваем остаток по модулю 5 (тогда возникает требование, что p не равно 5), так как по МТФ p⁴ дает остаток 1 по модулю 5. Вся левая часть, получается, дает остаток 2 по модулю 5. Теперь посмотрим на правую часть. Сразу видно, что второе слагаемое дает остаток 0 по модулю 5 (так как имеет вид 5*q). Что тогда можно сказать о n²?

Подсказка 3

Получается, n² должно давать остаток 2 по модулю 5. Рассмотрим различные случаи остатков. Какой вывод можем сделать?

Подсказка 4

Да, n² не может давать остаток 2 по модулю 5. Тогда у нас остается единственное возможное значение p: p = 5. Тогда наше уравнение превращается в квадратное, которое легко решается!

Показать ответ и решение

Согласно малой теореме Ферма, если p⁄= 5,  число p4  даёт остаток 1 при делении на 5. Число 211 также даёт остаток 1 при делении на 5. И 5pn  делится на 5.  Значит, если p⁄= 5,  мы получаем, что  2
n  даёт остаток 2 при делении на 5, что невозможно.

Осталось разобрать случай p =5.  В этом случае нам надо решить квадратное уравнение

 2
n  +25n− 625 − 211= 0

     −25±-√3125+-4⋅211
n1,2 =        2

Откуда получаем два решения: (p,n)=(5,−44)  и (p,n)= (5,19).

Ответ:

− 44,19

Ошибка.
Попробуйте повторить позже

Задача 11#122423

Три простые числа p,q  и r  больше трех и удовлетворяют условию 2p+ 5q = r.  Для какого наибольшего n  число p+q+ r  всегда будет делиться на n?

Источники: СПбГУ - 2025, 11.3(см. olympiada.spbu.ru)

Подсказки к задаче

Подсказка 1

Чтобы угадать ответ, попробуйте записать число p + q + r, используя равенство из условия.

Подсказка 2

Скорее всего, вы поняли, что работать надо с делимостью на 3. Быть может, повезёт и даже с девяткой получится.

Подсказка 3

Рассмотрите варианты остатков p и q при делении на 3. Чтобы доказать, что больше 9 нельзя, подберите два примера, чтобы НОД значений p + q + r был 9.

Показать ответ и решение

Покажем, что p+ q+ r  всегда делится на 9.  Действительно, по условию 2p+ 5q =r,  поэтому

p +q+ r= 3p+6q = 3(p+2q)

Заметим, что

2p+ 5q = 2(p+ q)+3q

поэтому если p  и q  дают остатки 1  и 2  от деления на три, то 2p+ 5q  делится на три и больше трех, поэтому r  не может быть простым числом. Значит, p  и q  дают одинаковые остатки от деления на три. Тогда p+ 2q  делится на три, а, значит, p+q+ r  делится на 9.

Подберем две различных тройки простых: если p =11  и q = 5,  то r= 2p+5q = 47  — простое число и p+q+ r= 63.  Если p= 17  и q = 5,  то r= 2p+ 5q =59  — простое число и p+ q+r =81.  Поэтому для чисел из условия задачи p+ q+r  гарантированно может делиться только на Н ОД(63,81)=9.

Ответ:

 9

Ошибка.
Попробуйте повторить позже

Задача 12#125072

Найдите все такие пары целых чисел m  и n >2  , что ((n − 1)!− n)⋅(n− 2)!= m(m − 2).

Источники: Всеросс, 2025, РЭ, 9.5 (см. olympiads.mccme.ru)

Подсказки к задаче

Подсказка 1:

Давай заметим, что в правой части равенства почти полный квадрат. Не хватает 1. Давайте добавим её слева и справа.

Подсказка 2:

Также хотелось бы разложить на скобочки левую часть, притом желательно на взаимно простые. Если не получается угадать разложение, рассмотрите выражение слева как квадратный трёхчлен относительно (n-2)!.

Подсказка 3:

Итак, вы получили равенство ((n - 1)! - 1)((n - 2)! - 1) = (m - 1)². Являются ли скобки в левой части взаимно простыми?

Подсказка 4:

Для дальнейших продвижения необходимо вспомнить, что если произведение взаимно простых чисел равно квадрату, то каждое из них является квадратом. Кстати, почему это так?

Подсказка 5:

Теперь осталось показать, что при больших n какая-то из скобок не сможет быть большим квадратом. Учитывая особенности факториалов, стоит подумать про остатки. Например, при делении на 4 квадраты могут иметь далеко не все остатки.

Показать ответ и решение

Заметим, что

((n − 1)!− 1)((n− 2)!− 1)=(n− 1)!⋅(n− 2)!− (n− 1)!− (n− 2)!+1 =

                      2               2
((n− 1)!− n)⋅(n − 2)!+ 1= m − 2m +1 =(m − 1) .

Пусть n> 4.  Заметим, что числа (n − 1)!− 1  и (n− 2)!− 1  взаимно просты. Предположим, что это не так, и оба этих числа делятся на простое число p.  Тогда число

(n− 1)!− 1− ((n− 2)!− 1)⋅(n− 1)= n− 2

тоже делится на p.  Тогда (n− 2)!  делится на p,  а (n− 2)!− 1  не кратно p,  противоречие. Таким образом, произведение взаимно простых чисел (n − 1)!− 1  и (n− 2)!− 1  —– точный квадрат, тогда и каждое из них точный квадрат. Однако, число (n − 1)!− 1  при n >4  даёт остаток 3 при делении на 4, поэтому оно точным квадратом быть не может. Остаётся разобрать случаи n ≤ 4.  При n= 4  получается (m − 1)2 = 5,  решений нет. При n =3  мы получаем: (m − 1)2 = 0,  что даёт единственное решение m = 1  , n =3.

Ответ:

 m = 1,n = 3.

Ошибка.
Попробуйте повторить позже

Задача 13#126313

Найти все натуральные числа n ≥3  такие, что для любого целого числа m ≥0  существуют n  целых чисел x,...,x
1     n  таких, что x1+ ⋅⋅⋅+ xn = 0  и x1x2+ x2x3+⋅⋅⋅+  xn−1xn+ xnx1 = −m.  Среди чисел x1,...,xn  могут быть совпадающие.

Источники: Всесиб - 2025, 10.4 ( см. sesc.nsu.ru)

Подсказки к задаче

Подсказка 1

Давайте попробуем пойти снизу-вверх. Что, если n = 3?

Подсказка 2

Попробуйте обозначить x₁, x₂ и x₃. Какими должны быть это обозначения, чтобы x₁ + x₂ + x₃ = 0?

Подсказка 3

Например, x₃ = - x₁ - x₂.

Подсказка 4

Попробуйте посмотреть на остатки от деления.

Подсказка 5

Быть может, с n = 4 нам подойдут аналогичные иксы?

Подсказка 6

Попробуйте увидеть полный квадрат.

Подсказка 7

Кажется, что с n = 5 противоречий не находится. Может, стоит попробовать придумать пример в общем виде?

Подсказка 8

Нам бы хотелось, чтобы сумма попарных произведений по циклу равнялась -m... То есть, вероятно, m должно быть среди иксов.

Подсказка 9

А давайте вспомним пример для n = 3.

Подсказка 10

Чтобы он работал и для n = 4, можно, например, докинуть 0.

Подсказка 11

А можем ли мы при помощи 0 доказать, что и для n ≥ 5 условия выполняются?

Показать ответ и решение

Пусть n =3.

Положим x1 = a,x2 =b,x3 = −a− b,  тогда

x1x2+ x2x3+ x3x1 =ab− b(a +b)− a(a+ b) =

    2   2
= −a − b − ab= −m

m = a2+ b2+ ab= (a − b)2+3ab

Из последнего равенства следует, что остаток от деления числа m  на 3 совпадает с остатком от деления (a − b)2  на 3, а он может быть равен только 0 и 1. Следовательно, числа − m  для всех m,  дающих при делении на 3 остаток 2, не могут быть представлены требуемым в условии образом, поэтому n =3  не подходит.

Пусть n= 4.

Положим x1 = a,x2 =b,x3 = c,x4 = d= −a − b− c.  Тогда

ab+bc+ cd +da= (a+c)(b+ d)=

=− (a +c)2 =− m

m =(a+ c)2

Следовательно, в требуемом в условии виде представляются только те числа − m,  для которых m  является точным квадратом, поэтому случай n = 4  тоже нам не подходит.

Пусть n≥ 5

Для произвольного m ≥ 0  рассмотрим n  целых чисел:

{− m;1;0;m − 1;0;0;...;0}

Их сумма равна 0, а сумма попарных проиведений по циклу равна − m,  следовательно, любое n≥ 5  удовлетворяет условию задачи.

Ответ:

 n ≥5

Ошибка.
Попробуйте повторить позже

Задача 14#126643

Коля выписал каждый натуральный делитель числа 2025n  по одному разу, после чего покрасил некоторые из них в красный цвет, а остальные — в синий. При этом он действовал так, чтобы разность между суммой всех красных делителей и суммой всех синих делителей оказалась минимально возможным (при данном n  ) положительным числом. Какими могут оказаться две последние цифры этой разности? (Найдите все варианты и докажите, что других нет.)

Источники: ФЕ - 2025, 10.5 ( см. www.formulo.org)

Подсказки к задаче

Подсказка 1

Разложите 2025 на простые множители. Как выглядит сумма всех его делителей? Почему максимальный делитель 2025ⁿ больше суммы остальных? Сумма делителей растёт медленнее, чем само число, из-за степеней в разложении.

Подсказка 2

Чтобы разность сумм красных и синих делителей была минимальной положительной, как нужно раскрасить делители? Что произойдёт, если покрасить только 2025 в красный, а остальные — в синий? Разность будет 2 × 2025ⁿ.

Подсказка 3

Докажите, что искомая разность = 70n + 81 (mod 100). Какие остатки при делении на 100 могут быть у 70n + 81 при разных n? Переберите n от 1 до 20. Остатки будут циклически повторяться!

Показать ответ и решение

Если n = 0,  разность равна 1.  Пусть n >0.  Сумма всех делителей числа 2025 равна

       2      4n        2      2n
(1 +3+ 3 + ...+ 3 )(1+ 5+ 5 +...+5  )=

                    n−1              n−1
=(1+ 120(1+ 81+...+81   ))(1 +30(1 +25+ 25  ))≡

≡ 1+ 120n+ 30(6+ 5n)≡ 81 +70n (mod 100)

По формуле суммы геометрической прогрессии, сумма делителей меньше, чем

(     ) (     )
 34n⋅ 3  52n⋅ 5 =2025n⋅ 15
     2       4         8

Значит, максимальный делитель (само число 2025n)  превосходит сумму остальных, поэтому для получения минимального положительного результата перед ним должен стоять плюс, а перед остальными делителями — минус. Получается, что ответ имеет вид 50− 81− 70n (mod 100) ∈ {9;19;29;39;49;59;69;79;89;99}.  Заметим, что разность больше 2025
 8  > 9,  то есть по крайней мере двузначная.

Ответ:

1, 09, 19, 29, 39, 49, 59, 69, 79, 89, 99

Ошибка.
Попробуйте повторить позже

Задача 15#126939

Докажите, что для каждого натурального a >1  существует простое p  такое, что число 1+ a+ a2+ ...+ap−1  — составное.

Показать доказательство

Заметим, что для a= 2  подойдет p= 11,  действительно:

0   1      10
2 +2 + ...+ 2 = 2047=23⋅89.

Далее a >2.

Выберем в качестве p  простой делитель числа a− 1>1.  Тогда:

1+a +a2+ ...+ ap−1 ≡1 +1+ ...+ 1≡ 0 (mod p).
                  ◟----◝◜p----◞

Значит, наше число кратно p,  осталось лишь показать, что это число больше p.  Это действительно так, поскольку a  уже больше p.

Ошибка.
Попробуйте повторить позже

Задача 16#127166

Покажите, что при всех натуральных a,n> 1  число φ(an − 1)  делится на n  .

Показать доказательство

Рассмотрим модуль m= an− 1.  Заметим, что:

     n
НОД(a − 1,a)= НОД (1,a)= 1

Значит, применима теорема Эйлера aφ(m) ≡ 1 (mod m).

С другой стороны ordm a= n,  так как при k <n  имеем ak < an− 1.  Тогда получаем, что n  делит φ(an− 1),  что и требовалось.

Ошибка.
Попробуйте повторить позже

Задача 17#127175

Найдите все натуральные n,  для которых числа n  и 2n− 1  имеют один и тот же набор простых делителей.

Подсказки к задаче

Подсказка 1.

Рассмотрите простой делитель p у числа n. Как можно использовать, что 2ⁿ−1 делится на p?

Подсказка 2.

Правильно! Ввести показатель и получить условия на него.

Подсказка 3.

Получаем, что n и p−1 делятся на этот показатель, а дальше непонятно, что делать... Было бы отлично, если бы n и p−1 были взаимно просты.

Подсказка 4.

Воспользуйтесь принципом крайнего на стадии выбора p.

Показать ответ и решение

Очевидно, что n = 1  подходит. Пусть теперь n≥ 2,  рассмотрим минимальный простой делитель p  числа n.  Пусть ord 2= s.
  p  Тогда φ(p)  делится на s,  то есть p− 1  делится на s.  По условию  n
2 − 1  делится на p,  значит, n  делится на s.  Заметим, что (n,p− 1)= 1,  так как p  — минимальный простой делитель n.  Отсюда получаем, что s= 1,  значит,  1
2 − 1= 1  делится на p.  Получаем противоречие, значит, таких n≥ 2  не существует.

Ответ:

 n =1

Ошибка.
Попробуйте повторить позже

Задача 18#127177

Докажите, что для простого p  уравнение ap +bp = cp  не имеет решений в натуральных числах при a  , b  , c≤ p.

Подсказки к задаче

Подсказка 1

Иногда полезно рассмотреть крайние случаи. Может ли равенство достигаться, если одно из чисел равно p?

Подсказка 2

Если ни одно из чисел не равно p, то они точно меньше. Может тогда посмотреть на делимость, ведь у нас есть малая теорема Ферма.

Подсказка 3

Из малой теоремы Ферма легко получается, что a + b ≡ c (mod p). Но все числа меньше p, какие есть варианты?

Подсказка 4

Полезно бы сравнить aᵖ + bᵖ и cᵖ при полученных условиях, кажется одна из частей будет намного больше другой.

Показать доказательство

Предположим противное: пусть существуют натуральные числа a,b,c≤p,  удовлетворяющие уравнению ap+bp = cp.

Рассмотрим случаи, когда одно из чисел a,  b,  c  равно p.

Пусть a= p.  Тогда  p   p  p
p + b = c.  Так как c≤ p,  то p   p
c ≤p .  Следовательно,

 p  p   p     p   p
p +b ≥ p + 1> p ≥c ,

что невозможно. Аналогично для b= p.

Пусть c=p,a⁄= p,b ⁄=p.  Тогда

 p   p       p   p
a  +b ≤ 2(p− 1) <p ,

так как

(-p--)p = (1+--1-)p > 1+--p-> 2.
 p− 1        p− 1       p− 1

Теперь a,b,c< p  и p  – простое, значит, a,b,c  не делятся на p.  По малой теореме Ферма:

ap ≡a  (mod p),  bp ≡b  (mod p),   cp ≡ c (mod p).

Подставляя в исходное уравнение, получаем:

a +b≡ c (mod p).

Так как 1≤ a,b,c≤ p− 1,  то 2≤a +b≤ 2(p− 1).  Возможны два случая:

  • a +b= c,
  • a +b= c+ p.

а) Пусть a+b= c.

Тогда ap +bp = (a +b)p.  По биному Ньютона:

(a +b)p =ap +bp+ p−∑ 1(p)ap−kbk > ap +bp,
               k=1 k

так как все дополнительные слагаемые положительны при a,b> 0  и p >1.

б) Пусть a+b= c+ p.

Обозначим s= a+ b,  тогда c =s− p, 2p− 1>s >p.  Уравнение принимает вид:

 p  p       p
a +b = (s− p) .

При фиксированном s  минимум ap+ bp  достигается при a =b = s,
       2  и тогда

 p   p   (s)p   1−pp
a  +b ≥ 2 2  = 2  s .

Рассмотрим убывающую при x> p  функцию

     (  x )p
f(x)=  x-− p  .

Так как функция убывает, то

           (  )p
f(s)> f(2p)=  2p  = 2p > 2p− 1 =⇒
             p

21−psp > (s− p)p = cp,

что завершает доказательство.

Ошибка.
Попробуйте повторить позже

Задача 19#127237

Как изменятся частное и остаток, если делимое и делитель увеличить в 5  раз?

Показать ответ и решение

Пусть число a  даёт остаток r  при делении на b,  то есть a= b⋅c+ r.  Увеличим делимое в пять раз, тогда получим 5a= 5b⋅c+ 5r.  Так как по условию делитель стал равен 5b,  видим, что частное осталось неизменным, а остаток увеличился в пять раз. Важно отметить, что так как 0 ≤r <b,  0≤ 5r< 5b,  то есть 5r  действительно является остатком при делении на 5b.  В силу однозначности определения остатка полученный нами результат — единственно возможный.

Ответ:

Остаток увеличиться в пять раз

Ошибка.
Попробуйте повторить позже

Задача 20#127238

Число a  даёт остаток 3  при делении на 5.  Какой остаток оно может давать при делении на 15?

Показать ответ и решение

По условию a= 5c+ 3,  пусть частное при делении a  на 15 равно x,  а остаток равен r,  то есть a =15x+ r.  Приравняем правые части имеющихся равенств:

5c+ 3= 15x+ r

5c− 15x= r− 3

Заметим, что 5c− 15x  кратно пяти, а, значит, r− 3  тоже нацело делится на 5. Учитывая, что r  — остаток при делении на 15, то есть 0 ≤r< 15,  получаем три возможных варианта: r= 3;  8;  13.

В самом деле, число a =3  имеет остаток 3 при делении на 5 и 15, число a= 8  имеет остаток 3 при делении на 5 и остаток 8 при делении на 15, и наконец, число a= 13  имеет остаток 3 при делении на 5 и остаток 13 при делении на 15.

Ответ:

3; 8; 13

Рулетка
Вы можете получить скидку в рулетке!