2014 dxdy logo

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

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




 
 Задачка по теории чисел (доказательство)
Сообщение09.06.2013, 19:28 
Задача:
Пусть $m$ и $n$ - натуральные числа, отличные от единицы, и такие, что $n^3 - 1$ делится на $m$ и $m - 1$ делится на $n$.
Доказать:
$m = n^2 + n + 1$
или
$m = n^3/2 + 1$

Вот ход моих рассуждений:
1) Начальные условия
$n^3 - 1 = 0 \mod m$
$m - 1 = 0 \mod n$
По формуле разности кубов имеем: $n^3 - 1 = (n - 1)(n^2 + n + 1) = 0 \mod m$
Остаток произведения равен произведению остатков:
$xy = 0$
$(n - 1) = x \mod m$
$(n^2 + n + 1) = y \mod m$

Очевидно что $n < m ; x = n - 1 ; y = 0$

Имеем:
$n^2 + n + 1 = 0 \mod m$
$m - 1 = 0 \mod n$

имеем свойство $a = b \mod m \Leftrightarrow ka = kb \mod km$ для любого натурального $k$
применим его:
$(n^2 + n + 1)n = 0 \mod mn$
$(m - 1)m = 0 \mod mn$
Перемножим два сравнения:
$(n^2 + n + 1)mn(m - 1) = 0 \mod mn$ ; $m - n^2 - n - 1 = 0 \mod mn$ ; $m = n^2 + n + 1 + tmn$, $t$ - целое.

$m = (n^2 + n + 1)/(1 - tn)$ ; $t \leqslant 0 $
$-n < t \leqslant 0$ т.к. при $t \leqslant -n$ дробь стремится к нулю при $n \to\infty$.
Отношение $(n^2 + n + 1)/(1 - tn)$ будет принимать натуральные значения только при $t = 0$ ; $m = n^2 + n + 1$.

Вопросы:
1) Я чувствую, что неправомерно воспользовался свойствами произведения остатков.
2) Что делать со вторым? как доказать что $m = n^3/2 + 1$? Были мысли по поводу теоремы Эйлера, но не знаю как доказать взаимную простоту чисел.

 
 
 
 Re: Задачка по теории чисел (доказательство)
Сообщение09.06.2013, 20:15 
Если $m= \frac {n^3}2+1$, то целое число $K= \frac {n^3-1}{\frac {n^3}2+1}<2$ и, следовательно, равно 1, что невозможно.

 
 
 
 Re: Задачка по теории чисел (доказательство)
Сообщение09.06.2013, 20:39 
К сожалению, только сегодня зарегистрировался на вашем сайте, еще не совсем освоил синтаксис.
Во втором задании опечатка, там $m = n^{3/2} + 1$

 
 
 
 Re: Задачка по теории чисел (доказательство)
Сообщение09.06.2013, 20:41 
Аватара пользователя
Я Вас поздравляю :-)
Если хотите решить сами - просто не читайте всё.

 
 
 
 Re: Задачка по теории чисел (доказательство)
Сообщение09.06.2013, 20:54 
Deggial
Огромное спасибо, уже долго мучаюсь над этой задачей, не думал о таком подходе к ней.
Недостаточно тех знаний, что я имею :(

 
 
 
 Re: Задачка по теории чисел (доказательство)
Сообщение10.06.2013, 14:11 
Еще раз добрый вечер, хотелось бы немного поговорить еще об этой задаче.
Нашел ее решение в журнале "Квант" №2 за 2002 год.
Задача номер М1787*
http://kvant.mccme.ru/pdf/2002/02/kv0202solutions.pdf
Мне непонятен следующий вывод: из того, что $p = (q^3 - 1)/(ql - 1)$ следует делимость на $ql - 1 $ чисел $q^2 - l$ и $q - l^2$.
Не могли бы вы пояснить мне этот шаг?

 
 
 
 Re: Задачка по теории чисел (доказательство)
Сообщение10.06.2013, 17:29 
Terrore в сообщении #734990 писал(а):
Мне непонятен следующий вывод: из того, что $p = (q^3 - 1)/(ql - 1)$ следует делимость на $ql - 1 $ чисел $q^2 - l$ и $q - l^2$.
Не могли бы вы пояснить мне этот шаг?
Например так:
$ql-1\mid q^3-1 \Rightarrow$
$ql-1\mid q^3l-l \Rightarrow$
$ql-1\mid q^2((ql-1)+1)-l \Rightarrow$
$ql-1\mid q^2-l$
2-й вывод аналогичен - сделайте в качестве упражнения.

 
 
 
 Re: Задачка по теории чисел (доказательство)
Сообщение11.06.2013, 07:36 
Благодарю за советы, все стало очевидно.

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


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