2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Модулярная арифметика
Сообщение22.07.2019, 19:28 
Заслуженный участник


20/12/10
8858
Пусть $p>2$ --- простое число. Для целых $a$ рассмотрим сумму $$S(a)=\sum_{k=1}^{p-1}\frac{a^k}{k}.$$ Вычислите $S(4)+S(3)-3S(2) \bmod{p}$.

 Профиль  
                  
 
 Re: Модулярная арифметика
Сообщение22.07.2019, 19:49 


05/09/16
11461

(ответ)

Ноль

 Профиль  
                  
 
 Re: Модулярная арифметика
Сообщение22.07.2019, 20:00 
Заслуженный участник


20/12/10
8858
wrest
Ответ верный. Напишите доказательство?

 Профиль  
                  
 
 Re: Модулярная арифметика
Сообщение22.07.2019, 21:33 
Модератор
Аватара пользователя


11/01/06
5660
Можно попробовать так:
$$S(a) = \sum_{k=1}^{p-1} \int_0^a x^{k-1}dx = \int_0^a dx \frac{x^{p-1}-1}{x-1}$$
Положим
$$I(f(x),L,U) := \int_L^U (x^{p-1}-1) f(x)\,dx$$
Тогда
$$I(f(x),L,U) \equiv I( 2f(2x), \frac{L}2, \frac{U}2)\pmod{p}$$
$$I(f(x),L,U) \equiv I( \frac{x}{x+1} f(x+1), L-1, U-1)\pmod{p}$$
$$I(f(x),L,U) \equiv I( \frac{x}{x-1} f(x-1), L+1, U+1)\pmod{p}$$
Осталось вычислить $I(\frac{1}{x-1},0,4) + I(\frac{1}{x-1},0,3) - 3I(\frac{1}{x-1},0,2)$.

 Профиль  
                  
 
 Re: Модулярная арифметика
Сообщение22.07.2019, 21:58 
Заслуженный участник


20/12/10
8858
maxal в сообщении #1406487 писал(а):
Осталось вычислить $I(\frac{1}{x-1},0,4) + I(\frac{1}{x-1},0,3) - 3I(\frac{1}{x-1},0,2)$.
Не вижу пока, как. Это делается?

А вообще, с интегралами мысль интересная. Мне тоже поначалу хотелось чего-то в этом духе (преобразование Абеля). Но потом я вспомнил одну старую задачу, и все прояснилось: ведь можно получить простую замкнутую формулу для $S(a) \bmod{p}$.

 Профиль  
                  
 
 Re: Модулярная арифметика
Сообщение22.07.2019, 22:46 


05/09/16
11461
nnosipov в сообщении #1406473 писал(а):
Ответ верный. Напишите доказательство?

Я на калькуляторе проверял :oops:

 Профиль  
                  
 
 Re: Модулярная арифметика
Сообщение22.07.2019, 22:49 
Заслуженный участник


20/12/10
8858
wrest в сообщении #1406501 писал(а):
Я на калькуляторе проверял :oops:
Тоже интересно: взять какое-нибудь 100-значное $p$ и проверить.

 Профиль  
                  
 
 Re: Модулярная арифметика
Сообщение22.07.2019, 23:01 


05/09/16
11461
nnosipov в сообщении #1406503 писал(а):
Тоже интересно: взять какое-нибудь 100-значное $p$ и проверить.

Проверил до $p=10007$

 Профиль  
                  
 
 Re: Модулярная арифметика
Сообщение22.07.2019, 23:03 
Заслуженный участник
Аватара пользователя


22/01/11
2641
СПб
я что-то не понимаю... Если $p=3$, то число
nnosipov в сообщении #1406466 писал(а):
$S(4)+S(3)-3S(2)$
равно $15/2$, то есть не является целым.

 Профиль  
                  
 
 Re: Модулярная арифметика
Сообщение22.07.2019, 23:14 
Заслуженный участник


20/12/10
8858
wrest в сообщении #1406506 писал(а):
Проверил до $p=10007$
Это понятно, что Вы проверили до некоторой разумной (для прямого счета) границы. Собственно, вот содержательный вопрос: как подсчитывать $S(a) \bmod{p}$ при больших $p$? В некотором смысле это даже интересней, чем решать исходную задачу.

alcoholist
Имеются в виду арифметические операции по модулю $p$ (сумму вычисляем не в $\mathbb{Q}$, а в $\mathbb{Z}_p$).

 Профиль  
                  
 
 Re: Модулярная арифметика
Сообщение23.07.2019, 06:12 
Модератор
Аватара пользователя


11/01/06
5660
nnosipov в сообщении #1406490 писал(а):
Не вижу пока, как. Это делается?

Я тоже теперь не вижу. :|

 Профиль  
                  
 
 Re: Модулярная арифметика
Сообщение23.07.2019, 06:52 
Заслуженный участник


20/12/10
8858
nnosipov в сообщении #1406490 писал(а):
ведь можно получить простую замкнутую формулу для $S(a) \bmod{p}$.
На самом деле, и это вычисление тоже было представлено на форуме, правда в неявной форме: см. http://dxdy.ru/post892365.html#p892365

 Профиль  
                  
 
 Re: Модулярная арифметика
Сообщение23.07.2019, 08:12 
Модератор
Аватара пользователя


11/01/06
5660
Ага, я чуть-чуть до этого не дошел, все пытался что-то подобное по модулю $p$ сделать, а тут оказывается надо играть на повышение:
$$pS(a) \equiv \sum_{k=1}^{p-1} (-1)^{k-1}\binom{p-1}{k-1} \frac{p}{k} a^k = \sum_{k=1}^{p-1} (-1)^{k-1} \binom{p}{k}a^k = a^p + (1-a)^p - 1\pmod{p^2}$$
Соответственно:
$$pS(4) + pS(3) - 3pS(2) \equiv (4^p - 3^p - 1) + (3^p - 2^p - 1) - 3(2^p - 2) \equiv 4^p - 4\cdot 2^p + 4 \equiv (2^p - 2)^2\equiv 0 \pmod{p^2}.$$
Красиво!

 Профиль  
                  
 
 Re: Модулярная арифметика
Сообщение23.07.2019, 09:41 
Заслуженный участник


20/12/10
8858
Да, мне тоже понравилось, поэтому и решил поделиться. Первоисточник: Problem Shortlist IMO 2011 Там есть еще одно решение, без явной формулы для $S(a)$.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 14 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group