2014 dxdy logo

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

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




 
 Интересная связь между периодом чисел обратных к простым
Сообщение03.09.2014, 18:38 
Игрался тут с вольфрамом и обнаружил интересную связь
если взять период числа обратного к простому, переписать
в десятичную дробь. Потом поделить 1 на полученный период (без ведущих нулей)
в результате получим десятичную дробь в периодом равным
простому числу с некоторым количеством нулей
Например:
$$\frac{1}{23} = 0.(0434782608695652173913)$$
$$\frac{1}{434782608695652173913} = 0.00000000000000000000(2300000000000000000000)$$
Как это можно объяснить?
И вообще есть-ли какая-то связь между простым числом и длиной периода?

 
 
 
 Re: Интересная связь между периодом чисел обратных к простым
Сообщение03.09.2014, 18:55 
Аватара пользователя
Длина периода числа $1/p$ равна мультипликативному порядку $10$ по модулю $p$. При этом сам период равен $m=\frac{10^q-1}{p}$, где $q$ - длина периода.
Нетрудно видеть, что $m$ делит $10^q-1$, поэтому длина периода $1/m$ делит $q$. В частности, если эта длина равна $q$, то сам период равен $\frac{10^q-1}{m}=p$.

 
 
 
 Re: Интересная связь между периодом чисел обратных к простым
Сообщение03.09.2014, 19:02 
Noctus в сообщении #903433 писал(а):
если взять период числа обратного к простому ...
Думается, так будет для любого числа, взаимно простого с $10$, простота здесь не важна.
Noctus в сообщении #903433 писал(а):
И вообще есть-ли какая-то связь между простым числом и длиной периода?
Это сложный вопрос, который сводится к отысканию порядка числа $10$ по модулю данного простого числа $p$. Этот порядок всегда является делителем $p-1$. Для некоторых $p$ он равен $p-1$, но как описать такие $p$, неизвестно.

 
 
 
 Re: Интересная связь между периодом чисел обратных к простым
Сообщение03.09.2014, 19:08 
А есть алгоритмы для вычисления мультипликативного порядка или нужно перебирать все числа до $p -1$?

 
 
 
 Re: Интересная связь между периодом чисел обратных к простым
Сообщение03.09.2014, 19:12 
Noctus в сообщении #903446 писал(а):
А есть алгоритмы для вычисления мультипликативного порядка или нужно перебирать все числа до p-1?
Алгоритмы есть, но они неэффективны. Поэкспериментируйте со 100-значными простыми числами.

 
 
 
 Re: Интересная связь между периодом чисел обратных к простым
Сообщение03.09.2014, 19:38 
Аватара пользователя
nnosipov в сообщении #903447 писал(а):
Алгоритмы есть, но они неэффективны.

Очень даже эффективны, если известна факторизация $p-1$. В неё на самом деле всё и упирается.

 
 
 [ Сообщений: 6 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group