2014 dxdy logo

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

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


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Факторизация. Теория чисел
Сообщение11.10.2017, 14:34 
Аватара пользователя


26/11/14
754
Всем доброго времени суток. Уважаемые помогите разобраться. Решаю задачу: Сколько существует натуральных чисел $n \leqslant 100000$, для которых число $ 2^n - n^2 $ делится на $7$?
Рассматриваю периодичность остатков от деления на $7 $ двух выражений: $2^n$ и $и n^2 $. Каждое множество разбилось на периодические последовательности. Общий период для этих двух, т.е. период появления остатков для: $ 2^n - n^2 $ нашел как: $T=$НОК$(T_1, \, T_2)$ , где: $(T_1, \, T_2)$ - периоды соответственно указанных выражений. Далее внутри периода $T $ нахожу $n$ , для которых эти выражения равноостаточны и поэтому $ 2^n - n^2 $ делится на $7$. Потом подсчитываю количество периодов в $100000$ , не забыв "недопериоды" и т.д. Здесь вроде понятно.

Возник другой вопрос. По сути, с помощью целочисленных функций: $f(n)=2^n\bmod 7; \, g(n) = n^2\bmod 7; \, s(n)= (f(n)-g(n))\bmod 7$ я представляю все множество натуральных чисел в виде периодической последовательности. У меня возник вопрос: любые ли функции позволяют получить по $\bmod m$ периодические последовательности остатков?

P.S. Пока не могу более четко сформулировать вопрос. По моему, в такой трактовке это не похоже на разбиение на классы? Натолкните на мысль. И где об этом почитать?

 Профиль  
                  
 
 Re: Факторизация. Теория чисел
Сообщение11.10.2017, 14:43 
Заслуженный участник
Аватара пользователя


23/07/05
17973
Москва
Stensen в сообщении #1254767 писал(а):
любые ли функции позволяют получить по $\bmod m$ периодические последовательности остатков?
Если класс допустимых функций никак не ограничивать, то, разумеется, нет.

Stensen в сообщении #1254767 писал(а):
в такой трактовке это не похоже на разбиение на классы?
Собственно, почему нет? Если есть отношение эквивалентности, то есть и разбиение на классы.

 Профиль  
                  
 
 Re: Факторизация. Теория чисел
Сообщение11.10.2017, 14:52 
Аватара пользователя


26/11/14
754
Someone в сообщении #1254772 писал(а):
Stensen в сообщении #1254767 писал(а):
любые ли функции позволяют получить по $\bmod m$ периодические последовательности остатков?
Если класс допустимых функций никак не ограничивать, то, разумеется, нет.


Извиняюсь: допустимые функции, это какие? Можете привести пример разбиения на непериодические последовательности?

 Профиль  
                  
 
 Re: Факторизация. Теория чисел
Сообщение11.10.2017, 15:13 
Заслуженный участник
Аватара пользователя


09/09/14
6328
Stensen в сообщении #1254775 писал(а):
Можете привести пример разбиения на непериодические последовательности?
Например, $\pi(n)$ -- $n$-я цифра в десятичной записи числа $\pi $. Вы не сможете построить какое-нибудь "разбиение на периодические последовательности" (что бы оно не значило) для этой функции.

 Профиль  
                  
 
 Re: Факторизация. Теория чисел
Сообщение11.10.2017, 15:17 
Заслуженный участник
Аватара пользователя


23/07/05
17973
Москва
Stensen в сообщении #1254775 писал(а):
допустимые функции, это какие?
А которые лично Вы пожелаете счесть таковыми.

 Профиль  
                  
 
 Re: Факторизация. Теория чисел
Сообщение11.10.2017, 15:21 
Аватара пользователя


26/11/14
754
Спасибо, пока понятно.

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

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



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

Сейчас этот форум просматривают: lantza


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

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