2014 dxdy logo

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

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


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


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 из теории чисел
Сообщение04.05.2015, 11:54 
Аватара пользователя


26/11/14
754
Доброго всем времени суток.
Плз помогите разобраться. Решить в целых числах: $ 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 $.
Не могу понять откуда это следует?

 Профиль  
                  
 
 Re: из теории чисел
Сообщение04.05.2015, 12:05 
Заслуженный участник


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

 Профиль  
                  
 
 Re: из теории чисел
Сообщение04.05.2015, 12:12 
Заслуженный участник
Аватара пользователя


09/09/14
6328
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$, наверное); но пусть и это будет с объяснением другой ошибки.

 Профиль  
                  
 
 Re: из теории чисел
Сообщение04.05.2015, 12:52 
Заслуженный участник
Аватара пользователя


21/12/05
5903
Новосибирск
Вычтите 7 из обеих частей равенства.

 Профиль  
                  
 
 Re: из теории чисел
Сообщение04.05.2015, 17:47 


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

 Профиль  
                  
 
 Re: из теории чисел
Сообщение04.05.2015, 18:32 
Заслуженный участник
Аватара пользователя


21/12/05
5903
Новосибирск
victor.l, перебирайте ещё.

 Профиль  
                  
 
 Re: из теории чисел
Сообщение04.05.2015, 19:07 


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

 Профиль  
                  
 
 Re: из теории чисел
Сообщение04.05.2015, 19:13 
Заслуженный участник
Аватара пользователя


09/09/14
6328

(Оффтоп)

victor.l в сообщении #1011242 писал(а):
Полагаю автору темы должно быть понятно.

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

 Профиль  
                  
 
 Re: из теории чисел
Сообщение05.05.2015, 09:39 
Аватара пользователя


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

К Botу: Можно пояснить следующее высказывание:
bot в сообщении #1011134 писал(а):
Вычтите 7 из обеих частей равенства.

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

 Профиль  
                  
 
 Re: из теории чисел
Сообщение05.05.2015, 10:51 
Заслуженный участник
Аватара пользователя


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

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

 Профиль  
                  
 
 Re: из теории чисел
Сообщение05.05.2015, 10:59 
Заслуженный участник


20/12/10
8858
И на школьном уровне достаточно алгоритмов, но их можно обсуждать только после того, как будут ликвидированы пробелы в понимании основных терминов и понятий (типа "разделить одно число на другое число с остатком"). Вот это никуда не годится:
Stensen в сообщении #1011372 писал(а):
кот. при делении $ x^2+3 $ на 7 дают в остатках: $ 7k$.

 Профиль  
                  
 
 Re: из теории чисел
Сообщение05.05.2015, 11:14 
Аватара пользователя


26/11/14
754
nnosipov в сообщении #1011392 писал(а):
И на школьном уровне достаточно алгоритмов, но их можно обсуждать только после того, как будут ликвидированы пробелы в понимании основных терминов и понятий (типа "разделить одно число на другое число с остатком"). Вот это никуда не годится:

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

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

17 mod 5 = 2

 Профиль  
                  
 
 Re: из теории чисел
Сообщение05.05.2015, 11:17 
Заслуженный участник
Аватара пользователя


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

-- 05.05.2015, 11:19 --

nnosipov в сообщении #1011392 писал(а):
И на школьном уровне достаточно алгоритмов

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

 Профиль  
                  
 
 Re: из теории чисел
Сообщение05.05.2015, 11:37 
Заслуженный участник


20/12/10
8858
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$ --- приятное и, похоже, единственное исключение.

 Профиль  
                  
 
 Re: из теории чисел
Сообщение05.05.2015, 11:46 
Заслуженный участник
Аватара пользователя


21/12/05
5903
Новосибирск

(Оффтоп)

provincialka в сообщении #1011391 писал(а):
Метод bot -- красивая "обертка" для этой идеи

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 20 ]  На страницу 1, 2  След.

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



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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