close

Вход

Забыли?

вход по аккаунту

?

Структурная формула для последовательности остатков ax (mod m) и ее приложение к цепной дроби связанной с квадратичным невычетом по простому модулю.

код для вставкиСкачать
ЧЕБЫШЕВСКИЙ СБОРНИК
Посвящается 65-ой годовщине со дня рождения
профессора Сергея Михайловича Воронина
Том 12 Выпуск 1 (2011)
СТРУКТУРНАЯ ФОРМУЛА ДЛЯ
ПОСЛЕДОВАТЕЛЬНОСТИ ОСТАТКОВ
ax (mod m)
И Ењ ПРИЛОЖЕНИЯ К ЦЕПНОЙ
ДРОБИ, СВЯЗАННОЙ С КВАДРАТИЧНЫМ
НЕВЫЧЕТОМ ПО ПРОСТОМУ МОДУЛЮ
И. И. Ильясов (г. Актобе, Казахстан)
Для доказательства соответствующего результата приведем теоремы и леммы аналогичные в работе [2] без подробного обоснования.
Пусть 1 6 a < m, n целые, (a, m) = 1. Рассмотрим видоизмененный
алгоритм Евклида для этих чисел.
?
m = a · a1 ? w1 , 0 < w1 < w0 (a = w0 )
?
?
?
?
w0 = w1 a2 ? w2 , 0 < w2 < w1
?
......................., ....................
(1)
?
?
wn?2 = wn?1 an ? wn , 0 < wn < wn?1 , wn = 1
?
?
?
wn?1 = wn an+1 ? 0, wn+1 = 0
Ясно, что
a
=
m
1
(2)
1
a1 ?
a2 ?
1
..
.?
an ?
1
an+1
и ai > 2, i = 1, 2, ..., n + 1.
Определение
1.
x0 = 1, x1 = a1 , . . . , xk+1 = ak+1 xk ? xk?1 , . . . , xn+1 = an+1 xn ? xn?1 ,
y0 = 0, y1 = 1, . . . , yk+1 = ak+1 yk ? yk?1 , . . . , yn+1 = an+1 yn ? yn?1 .
94
И. И. ИЛЬЯСОВ
Замечание: Так как xi?1 yi ?xi yi?1 = 1 i = 1, 2, ..., n+1, то m = xn+1 , a = yn+1 .
Последовательность остатков rk : ak ? rk (mod m) (k =
= 0, 1, 2, ..., m ? 1) обозначим R (a, m) .
3 Последовательность w0 , w1 , ..., wn называется базисной
последовательностью R (a, m) .
Определение
2.
Определение
.
Ясно, что w0 > w1 > ... > wn = 1.
Лемма
1.
axk = wk + myk , k = 0, 1, ..., n.
Обозначение. ai ? 1 = pi , i = 1, 2, . . . , n + 1.
1 Каждое натуральное число x < m единственным образом
представляется в виде
.
Теорема
x = x0 t1 + x1 t2 + ... + xk tk+1
с условиями:
1) tk+1 6= 0;
2) 0 6 ti 6 pi, ti целые i = 1, 2, . . . , k + 1;
3) для любых i и j , где 1 6 i < j 6 k + 1 (k > 1)
(ti , ti+1 , . . . , tj?1 , tj ) 6= (pi , pi+1 ? 1, . . . , pj?1 ? 1, pj ).
И каждое число
x = x0 t1 + x1 t2 + ... + xk tk+1
с условиями 1), 2), 3) меньше m.
2 При 1 6 i < j 6 n + 1 (x?1 = 0)
Лемма
.
xj + xi?2 = xi?1 pi + xi (pi+1 ? 1) + ... + xj?2 (pj?1 ? 1) + xj?1 pj
Лемма
3.
При выполнении условии 1), 2), 3)
x = x0 t1 + x1 t2 + ... + xk tk+1 < xk+1 .
Следствие
1.
Если
x = x0 t1 + x1 t2 + ... + xk tk+1
0
0
x0 = x0 t1 + x1 t2 + ... + xk t0k+1
с условиями 1), 2), 3), то при tk+1 = t0k+1, ...,ti+1 = t0i+1, ti < t0i x < x0.
(3)
СТРУКТУРНАЯ ФОРМУЛА ДЛЯ ПОСЛЕДОВАТЕЛЬНОСТИ . . .
95
2 Каждое натуральное число l ? R(a, m) единственным образом представляется в виде
.
Теорема
l = w0 t1 + w1 t2 + ... + wk tk+1 ,
(4)
c условиями
1) tk+1 6= 0
2) 0 6 ti 6 pi, ti-целые, i = 1, 2, ..., k + 1
3) для любых i и j , где 1 6 i < j 6 k + 1
(k > 1) (ti , ti+1 , ..., tj?1 , tj ) 6= (pi , pi+1 ? 1, . . . , pj?1 ? 1, pj ).
И всякое число указанного вида с условиями 1), 2), 3) принадлежит
.
R(a, m)
Доказательство теоремы следует из следующих лемм.
Лемма
4.
При 1 6 i < j (w?1 = m)
wj + wi?2 = wi?1 pi + wi (pi+1 ? 1) + ... + wj?2 (pj?1 ? 1) + wj?1 pj .
Лемма
5. l
вида (4) с условиями 1), 2), 3) меньше m.
Доказательство.
(теоремы)
Возможность представления. Пусть x произвольное натуральное число.
По теореме 1 x представляется в виде
x = x0 t1 + x1 t2 + ... + xk tk+1
с условиями 1), 2), 3). По лемме 1
ax = a(x0 t1 + x1 t2 + ... + xk tk+1 ) = (ax0 )t1 + (ax1 )t2 + ... + (axk )tk+1 =
= (w0 + my0 )t1 + (w1 + my1 )t2 + ... + (wk + myk ) tk+1 =
= w0 t1 + w1 t2 + ... + wk tk+1 + m (y0 t1 + y1 t2 + ... + yk tk+1 )
По лемме 5
l = w0 t1 + w1 t2 + ... + wk tk+1 < m,
а y0 t1 + y1 t2 + ... + yk tk+1 неотрицательные целые, следовательно l ? R (a, m).
Пусть l = w0 t01 + w1 t02 + ... + ws t0s+1 .
Тогда
ax0 = a x0 t01 + x1 t02 + ... + xs t0s+1 = l + m y0 t01 + y1 t02 + ... + ys t0s+1 .
Единственность представления.
Следовательно, имеем
ax = l + my y = y0 t1 + ... + yk tk+1
ax0 = l + my 0 y 0 = y0 t01 + ... + ys t0s+1
96
И. И. ИЛЬЯСОВ
Отсюда
a(x ? x0 ) = m(y ? y 0 )
Так как x ? x0 по модулю меньше чем m и (a, m) = 1то отсюда следует, что
x = x0 и y = y 0 .
Тогда по теореме 1 s = k и t1 = t01 , t2 = t02 , . . . , tk+1 = t0k+1 . Теорема доказана.
Число x = x0t1 +x1t2 +...+xk tk+1 с условиями 1), 2), 3) называется координатой числа l = w0t1 +w1t2 +...+wk tk+1 в последовательности
R (a, m).
5 Пусть l и l0 ? R (a, m). Будем говорить, что l предше0
ствует l в R (a, m), если x < x0, где x и x0 соответствующие координаты l и
l0 в R (a, m). Предшествование l по отношению к l0 обозначается l ? l0 .
Определение
4.
Определение
.
Обозначения. M (T1 , T2 , ..., Tk ) - множество чисел l ? R (a, m) , l?w0 T1 +w1 T2 +
... + wk?1 Tk где T1 , T2 , ..., Tk с условиями 1), 2), 3) и
Mk = M (p1 ? 1, p2 ? 1, ..., pk?1 ? 1, pk ), k > 2
M1 = M (p1 )
Теорема
3.
Tk+1 ?1
M (T1 , T2 , ..., Tk , Tk+1 ) =
[
(Mk + wk tk+1 )
[
(M (T1 , T2 , ..., Tk ) + wk Tk+1 ). (5)
tk+1 =0
Разобьем множество M (T1 , ..., Tk , Tk+1 ) на два подмножества вида
первое: {w0 t1 + ... + wk?1 tk + w
k tk+1 } где tk+1 6 Tk+1 ? 1
0
второе: w0 t1 + w1 t2 + ... + wk?1 tk + wk tk+1
При tk+1 6 Tk+1 ? 1 для всевозможных значений t1 , t2 , ..., tk с условиями 1),
2), 3), включая (0, . . . , 0)
Доказательство.
w0 t1 + ... + wk?1 tk + wk tk+1 ? w0 T1 + ... + wk?1 Tk + wk Tk+1 .
так как
x0 t1 + ... + xk?1 tk + xk tk+1 < x0 T1 + ... + xk?1 Tk + xk Tk+1 .
С другой стороны для всевозможных значений t1 , t2 , ..., tk с условиями 1),
2), 3), включая (0, . . . , 0)
{w0 t1 + w1 t2 + ... + wk?1 tk } =k .
Действительно, во-первых, в силу x0 t1 + ... + xk?1 tk < xk
имеем, что
w0 t1 + w1 t2 + ... + wk?1 tk ? wk ,
СТРУКТУРНАЯ ФОРМУЛА ДЛЯ ПОСЛЕДОВАТЕЛЬНОСТИ . . .
97
во-вторых
x0 (p1 ? 1) + . . . + xk?2 (pk?1 ? 1) + xk?1 pk = xk ? 1.
Следовательно
x0 t1 + . . . + xk?1 tk 6 x0 (p1 ? 1) + . . . + xk?2 (pk?1 ? 1) + xk?1 pk
И по определению
{w0 t1 + w1 t2 + ... + wk?1 tk } =k для всевозможных значений t1 , t2 , ..., tk с условиями 1), 2), 3), включая (0, . . . , 0)
Поэтому первое подмножества совпадает с
Tk+1 ?1
[
(Mk + wk tk+1 )
tk+1 =0
Теперь, так как во втором подмножестве
w0 t1 + . . . + wk?1 tk + wk tk+1 ? w0 T1 + . . . + wk?1 Tk + wk Tk+1
то отсюда следует что
w0 t1 + . . . + wk?1 tk ? w0 T1 + . . . + wk?1 Tk ,
то есть второе подмножество содержится в
M (T1 , T2 , ..., Tk ) + wk Tk+1 .
Если же
w0 t1 + w1 t2 + ... + wk?1 tk + wk tk+1 ? M (T1 , T2 , ..., Tk ) + wk Tk+1 ,
то
x0 t1 + . . . + xk?1 tk 6 x0 T1 + ... + xk?1 Tk .
И следовательно
x0 t1 + . . . + xk?1 tk + xk Tk+1 6 x0 T1 + ... + xk?1 Tk + xk Tk+1 ,
то есть w0 t1 + w1 t2 + ... + wk?1 tk + wk tk+1 принадлежит второму подмножеству.
Теорема доказана.
Обозначение. R (na < l, m) обозначает множество чисел R (a, m) меньших l.
Теорема
4.
R (na < w0 , m) = R(w1 , w0 ).
98
И. И. ИЛЬЯСОВ
Доказательство. Пусть na ? w0 t1 + w1 t2 + ... + wk?1 tk + wk tk+1 (modm).
Если w0 t1 + w1 t2 + ... + wk?1 tk + wk tk+1 < w0 , то t1 = 0 т.е
na ? w1 t2 + ... + wk?1 tk + wk tk+1 (modm)
с условиями 1), 2), 3) для t2 , ..., tk+1 . Тогда по теореме 2 при a = w1 , m = w0
w1 t2 + ... + wk?1 tk + wk tk+1 ? R(w1 , w0 ). Верно и обратное утверждение.
Теорема доказана.
Из этой теоремы получаем последовательность
R (a, m) ? R(w1 , w0 ) ? R(w2 , w1 ) ? ...
Обозначения. x00 = 1, x01 = a2 , x02 = a3 x01 ? x00 , ..., x0n = an+1 x0n?1 ? x0n?2 ,
0
0
y00 = 0, y10 = 1, y20 = a3 y10 ? y00 , ..., yn0 = an+1 yn?1
? yn?2
Лемма
.
6. w1 x0n = wn+1 + w0 yn0 , n = 0, 1, 2, ...
Доказательство.
Доказательство аналогично доказательству леммы 1.
Следствие 1.
0
w1 (x00 t1 +x01 t2 +...+x0k?1 tk+1 ) = w1 t2 +...+wk?1 tk +wk tk+1 +w0 (y00 t1 +...+yk?1
tk+1 ).
Следствие 2.
... +
x0k?1 tk+1
Если x1 t2 + ... + xk tk+1 координаты l в R (a, m), то x00 t1 + x01 t2 +
координаты l в R (w1 , w0 ).
5 Если ? наименьший квадратичный невычет по простому модулю p > 2, то в разложении в полурегулярную цепную дробь
Теорема
.
?
=
p
1
1
a1 ?
a2 ?
... ?
1
an ?
1
an+1
ai 6 ?, i = 2, ..., n + 1.
Доказательство.
Пусть
p = w0 a1 ? w1 ,
w0 = w1 a2 ? w2 ,
.......................,
wn?2 = wn?1 an ? wn
wn?1 = 0n an+1 ? 0
0 < w1 < w0 (w0 = ?)
0 < w2 < w1
....................
0 < wn < wn?1 , wn = 1
wn+1 = 0
СТРУКТУРНАЯ ФОРМУЛА ДЛЯ ПОСЛЕДОВАТЕЛЬНОСТИ . . .
99
Из определения ? следует, что числа 1, 2, ..., ? ? 1 квадратичные вычеты по
модулю p.
По теореме 4 R (n? < w0 , m) = R(w1 , w0 ), следовательно множество чисел w1 t2 +
... + wk tk+1 с условию 1), 2), 3), совпадает с множеством чисел 1, 2, ..., ? ? 1. Так
как
? (x1 t2 + ... + xk tk+1 ) = w1 t2 +...+wk tk+1 (modp) и w1 t2 +...+wk tk+1 квадратичный
вычет по модулю pто x1 t2 +...+xk tk+1 квадратичный невычет по модулю p. Если
предположить что ai > ? при некотором i = 2, ..., n + 1, то отсюда получаем
? 6 pi и следовательно wi?1 ? ? R (w1 , w0 ) и это противоречие так как,wi?1 ?
должно быть меньше чем ?,следовательно ai 6 ? i = 2, ..., n.
Теорема доказана.
Отметим что из этой теоремы в силу x1 = a1 > ? легко получить известную
оценку
r
1
1
+ p.
?< +
2
4
Некоторые важные сведения об исследованиях наименьшего квадратичного
невычета по простому модулю можно найти в [1].
СПИСОК ЦИТИРОВАННОЙ ЛИТЕРАТУРЫ
[1] Гельфонд А. О., Линник Ю. В. Элементарные методы в аналитической теории чисел. М., Физматгиз, 1962 г., С. 214 220
[2] Ильясов И.И. Структурная формула для последовательности {n?} и ее некоторые приложения в вопросах теории чисел. // Чебышевский сборник. Т.11.
Вып.1-Тула: Изд-во Тул. гос. пед. ун-та им. Л.Н. Толстого. 2010. С. 152 172
Актюбинский государственный университет им. К. Жубанова
Поступило 13.06.2011
1/--страниц
Пожаловаться на содержимое документа