количество пар чисел, сумма квадратов которых делится на 49

[Whitaker]

Здравствуйте!
Сколько существует пар целых чисел $(x;y)$, заключенных между $1$ и $1000$, таких что $x^2+y^2$ делится на 49?
Я решил для случая, когда $x=y$. А для других случаев пока ничего неизвестно для меня. Подскажите пожалуйста.

С уважением, Whitaker.

-- Вт сен 20, 2011 09:54:07 --

Не знаю может пройдёт формула включений и исключений.
Нужно найти пары $(x;y)$ такие что $x^2+y^2=49k$.
Пусть для простоты $k=1$
Думаю, что Для начала нужно просто найти количество решений уравнения $x_1+x_2=49$ в натуральных числах и далее по формуле вкл и искл. Может быть моя идея является бредом.

[PAV]

Все проще гораздо, рассмотрите возможные остатки по модулю 7.

(Очевидно, что подходят любые пары, в которых оба числа делятся на 7. А вот будут ли кроме них еще какие-то?)

[Whitaker]

PAV извините за такой глупый вопрос.
Но почему вы рассматриваете остатки именно по модулю 7? А нельзя ли по модулю 49?

[Shadow]

Whitaker в сообщении #484396 писал(а):

PAV извините за такой глупый вопрос.
Но почему вы рассматриваете остатки именно по модулю 7? А нельзя ли по модулю 49?

Можно. Но по 7 проще будет

[Whitaker]

Рассмотрим сравнение по модулю $7$
$x^2+y^2\equiv 0 (mod 7)$
Очевидно числа $x^2$ и $y^2$ должны иметь следующие остатки
$(0;0), (1;6), (2;5), (3;4), (4;3), (5;2), (6;1)$

[Sonic86]

Whitaker в сообщении #484400 писал(а):

Рассмотрим сравнение по модулю $7$
$x^2+y^2\equiv 0 (mod 7)$
Очевидно числа $x^2$ и $y^2$ должны иметь следующие остатки
$(0;0), (1;6), (2;5), (3;4), (4;3), (5;2), (6;1),$

(синтаксис)

$a \equiv b \pmod m$

a \equiv b \pmod{m}

$a = b \mod m$

a = b \mod m

А возможно ли, чтобы $x^2 \equiv 2 \pmod 7$ или $y^2 \equiv 5 \pmod 7$
Кстати, если Вы знаете, как оперировать с $y^{-1}$, перебор можно существенно сократить .

[PAV]

А теперь посмотрите, какие в принципе остатки по модулю 7 может иметь квадрат числа.

[Whitaker]

Думаю, что $x^2 \equiv 2 \pmod{7}$ невозможно. но пока не знаю как это доказать. С задачами на остатки у меня часто возникают трудности.

[Sonic86]

Вы же можете решить такое сравнение (и не только такое, а вообще любое для заданного модуля) просто перебором значений $x$ - поле вычетов-то конечно, в отличие от $\mathbb{Z}, \mathbb{Q}, \mathbb{R}, \mathbb{C}$, что порою радует.

[Whitaker]

К сожалению решать сравнения я пока не могу

-- Вт сен 20, 2011 10:55:26 --

В ответе написано следующее: Если $x$ при делении на $7$ дает остатки $0,1,2,3,4,5,6,$ то квадрат дает остатки $0,1,4,2,2,4,1$. Поэтому $x^2+y^2$ делится на $7$ (а тем более на $49$) лишь в случае когда и $x$ и $y$ делятся на 7.

Непонятно одно почему рассматривают остатки от деления именно на 7?
Почему не на 6 или 8?

[Sonic86]

Whitaker в сообщении #484408 писал(а):

Непонятно одно почему рассматривают остатки от деления именно на 7?

Ну у нас же уравнение $x^2+y^2 \equiv 0 \pmod 7$ - по модулю 7.
Если обозначить для $b>0$ $a \mod b$ - остаток от деления $a$ на $b$, то можно записать $x^2 \mod 7 = (x \mod 7)^2 \mod 7$, а $x \mod 7$ принимает лишь 7 значений из $\{ 0;1;2;3;4;5;6\}$. Так понятней?

[Whitaker]

Да уже намного понятней Sonic86

[Shadow]

Whitaker в сообщении #484408 писал(а):

Непонятно одно почему рассматривают остатки от деления именно на 7?
Почему не на 6 или 8?

При анализе делимости выражения на составное число, обычно в первой очереди рассматривается делимость на его простые множители.

Ну например
При каких 1<=x,y<=1000, $x^2+y^2$ делиться на 35

[Whitaker]

При каких $1 \leq x,y \leq 1000$ выражение $x^2+y^2$ делится на 35?

Наверное рассматривают сравнения $x^2+y^2 \equiv 0 \pmod{5}$ и $x^2+y^2 \equiv 0 \pmod{7}$?
Нужно рассмотреть оба сравнения да? Или одного хватит?
Правильно ли я говорю?

[Sonic86]

Рассматривать нужно, конечно, оба.