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

[nnosipov]

Странно, что эта задача названа комбинаторной. Комбинаторная составляющая здесь близка к нулю, тогда как теоретико-числовая весьма существенна. Это из какого задачника?

[Whitaker]

Согласен с Вами nnosipov!
Я хотел назвать топик Задача по ТЧ. А задача из книжки Виленкина "Комбинаторика".

[nnosipov]

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

А задача из книжки Виленкина "Комбинаторика".

Понятно. Тогда имеет смысл эту задачу отложить, если есть намерение заниматься комбинаторикой. И вернуться к ней, когда будете целенаправленно заниматься теорией чисел (тогда она покажется нетрудным упражнением).

[Whitaker]

$x^2+y^2 \equiv 0 \pmod{7}$.
Отсюда получаем, что $x^2$ и $y^2$ при делении на $7$ должны иметь остатки: $(0,0), (1,6), (2,5), (3,4), (4,3), (5,2), (6,1)$.
Как я понял, но здесь подходит только первый случай когда числа $x^2$ и $y^2$ при делении на $7$ дает остаток 0. т.е. $x^2=7k_1$ и $y^2=7k_2$, получаем, что $x^2+y^2=7k_1+7k_2=7(k_1+k_2)$ Но ведь отсюда не следует, что $x^2+y^2$ делится на 49.
Или где-то ступил?

-- Вт сен 20, 2011 16:35:42 --

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

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

А задача из книжки Виленкина "Комбинаторика".

Понятно. Тогда имеет смысл эту задачу отложить, если есть намерение заниматься комбинаторикой. И вернуться к ней, когда будете целенаправленно заниматься теорией чисел (тогда она покажется нетрудным упражнением).

Ладно. Просто я некоторое время уже занимаюсь комбинаторикой по вышеуказанной книжке. А задачка мне стала интересной, но сам не смог решить. Вы правы здесь практически нет комбинаторики. А с ТЧ задачами я обычно не справляюсь так как еще не занимался теорией чисел.

[nnosipov]

Да, есть немножко. Итак, если $x^2+y^2$ делится на $7$, то, как Вы правильно показали, оба числа $x$ и $y$ должны делиться на $7$. Запишем $x=7x_1$ и $y=7y_1$, после чего подставим в $x^2+y^2$. Вот теперь должно быть понятно.

[Whitaker]

Так понятно nnosipov.
Но ведь я показал, что $x^2$ и $y^2$ должны делиться на 7, а не $x$ и $y$.

[ИСН]

Есть народная примета, что если квадраты чисел делятся на 7, то и сами числа, как правило...

[nnosipov]

На самом деле Вы показали, что $x$ и $y$ делятся на $7$, только не заметили этого

[Whitaker]

Да Да
Никогда не забуду больше эту народную примету
Спасибо Вам nnosipov и ИСН за помощь и внимание!