из теории чисел

[Stensen]

Доброго всем времени суток.
Плз помогите разобраться. Решить в целых числах: $ 7y = x^2 + 3 $. Пытался решить так: $ (\sqrt{7y} - x)(\sqrt{7y} + x) = 3 $. и пытался искать сомножители слева как: $ 1$\cdot 3 $, $ 3$\cdot 1 $, $ (-1) \cdot (-3) $, $ (-3)\cdot (-1)$. не получилось. В указаниях к решению сказано, что т.к. $ x^2 + 3 $ делится на 7 (т.к. слева 7y), то: $ x= 7\cdot k + 2 $ или $ x= 7\cdot k + 5 $.
Не могу понять откуда это следует?

[iifat]

Подставьте $y=7k+r$, пробегите $r$ от 0 до 6 и посмотрите, что получится.

[grizzly]

Stensen в сообщении #1011113 писал(а):

Пытался решить так: $ (\sqrt{7y} - x)(\sqrt{7y} + x) = 3 $. и пытался искать сомножители слева как: $ 1\cdot 3 $, $ $3\cdot 1 $, $ (-1) \cdot (-3) $, $ (-3)\cdot (-1)$. не получилось.

И не должно было. Иногда, конечно, можно случайно получить так частный случай решения. Но ведь в скобках не обязательно целые числа должны быть. Например, $ (\sqrt{7} - 2)(\sqrt{7} + 2) = 3 $ вполне себе даёт решение.

Stensen в сообщении #1011113 писал(а):

т.к. $ x^2 + 3 $ делится на 7 (т.к. слева 7y), то: $ x= 7\cdot k + 2 $ или $ x= 7\cdot k + 5 $.
Не могу понять откуда это следует?

А Вы $7k+2$ в выражение $ x^2 + 3 $ подставьте вместо $x$ и посмотрите, что получится. А потом подставьте другие ($7k, 7k+1, 7k+3$ и все остальные, сколько их может быть). Скорее всего, к этому моменту всё станет понятно.

-- 04.05.2015, 13:15 --

А, уже объяснили (только там должно быть $x=7k+r$, наверное); но пусть и это будет с объяснением другой ошибки.

[bot]

Вычтите 7 из обеих частей равенства.

[victor.l]

Переберите $x$ от $1$ до $6$ и получите $x =2+7t$

[bot]

victor.l, перебирайте ещё.

[victor.l]

Ну еще $5+7t$. Полагаю автору темы должно быть понятно.

[grizzly]

(Оффтоп)

victor.l в сообщении #1011242 писал(а):

Полагаю автору темы должно быть понятно.

Автору должно быть понятно красивое решение bot. А Вам -- что Вы третий раз в теме повторили то же решение "в лоб" без какой-либо изюминки

[Stensen]

Всем предельный спасиб!
Как я понял, нужно искать такие $x$ , кот. при делении $ x^2+3 $ на 7 дают в остатках: $ 7k$. Это такой общий подход? Где можно почитать про алгоритмы решения подобных задач (теорию, но не очень глубоко, на уровне школы)?

К Botу: Можно пояснить следующее высказывание:

bot в сообщении #1011134 писал(а):

Вычтите 7 из обеих частей равенства.

это действие основано на каком-то алгоритме или как можно догадаться, что нужно вычесть 7?

[provincialka]

Stensen
При решения диофантовых уравнений обычно приходится "догадываться" и подбирать метод почти к каждому уравнению отдельно (ну, это если "на уровне школы", на более высоком уровне есть и некие алгоритмы).

Обычные методы (на школьном уровне) -- делимость, остатки, разложение на множители и т.п. То, что правая часть должна делиться на 7 -- очевидно, и подобрать соответствующие $x$ легко. Метод bot -- красивая "обертка" для этой идеи. Обычное такие ходы находят уже после, при оформлении решения.

[nnosipov]

И на школьном уровне достаточно алгоритмов, но их можно обсуждать только после того, как будут ликвидированы пробелы в понимании основных терминов и понятий (типа "разделить одно число на другое число с остатком"). Вот это никуда не годится:

Stensen в сообщении #1011372 писал(а):

кот. при делении $ x^2+3 $ на 7 дают в остатках: $ 7k$.

[Stensen]

nnosipov в сообщении #1011392 писал(а):

И на школьном уровне достаточно алгоритмов, но их можно обсуждать только после того, как будут ликвидированы пробелы в понимании основных терминов и понятий (типа "разделить одно число на другое число с остатком"). Вот это никуда не годится:

А разве нет термина: деление чисел с остатком? Неполное частное и остаток? И как тогда правильно называть эту операцию?

17:5=3 (ост.=2) или

17 mod 5 = 2

[provincialka]

Stensen
И каков же может быть остаток? Почему он у вас от $k$ зависит?!

-- 05.05.2015, 11:19 --

nnosipov в сообщении #1011392 писал(а):

И на школьном уровне достаточно алгоритмов

Ну да, конечно... Просто они не такого уровня общности как, скажем, корни квадратного уравнения. Я хотела подчеркнуть, что решение диофантовых уравнений -- это все-таки немного искусство!

[nnosipov]

provincialka в сообщении #1011391 писал(а):

Метод bot -- красивая "обертка"

Не только. Если его сравнивать с методом перебора остатков $x$, то на поиск решения тратится примерно в два раза меньше операций. Правда, сама операция становится другой, так что общие трудозатраты вполне могут быть соизмеримы.

(Оффтоп)

На примере общего уравнения $py=x^2+3$ ($p=3k+1$ --- простое число) это выглядит так. Перебирая $x$ по первому методу и проверяя делимость $x^2+3$ на $p$, мы сделаем примерно $p/2$ тестов на делимость, пока не наткнёмся на нужный $x$. Перебирая $y$ по методу bot и проверяя, будет ли $py-3$ точным квадратом, мы совершим примерно $p/4$ тестов на "быть точным квадратом", пока не обнаружим нужный $y$. Что лучше? При маленьких $p$ оба метода хороши, а при больших $p$ оба плохи за счёт большого количества тестов (несмотря на то, что тест каждого типа стоит дешево).

-- Вт май 05, 2015 15:44:08 --

provincialka в сообщении #1011396 писал(а):

Просто они не такого уровня общности как, скажем, корни квадратного уравнения.

Я бы сказал "не такого уровня сложности". Плюс к этому, алгоритмы становятся слишком трудоёмкими с вычислительной точки зрения. Алгоритм Евклида для решения диофантовых уравнений $ax+by=c$ --- приятное и, похоже, единственное исключение.

[bot]

(Оффтоп)

provincialka в сообщении #1011391 писал(а):

Метод bot -- красивая "обертка" для этой идеи

Хм, обёртывающий метод - звучит недурно.