Остатки.

[pb_1989]

Доказать, что квадрат любого простого числа больше 5 при делении на 30 может дать в остатке только 19 или 1.


если представим простое число как $p=30n+r$
Остаток не может быть кратен 2,3,5, уберем все кратные им, тогда остаются остатки 7, 11, 13, 17, 19, 23, 29.
в нашем случае должно быть$r=1, r=19$

как тогда тут использовать условие что $p>5$?

[alex1910]

pb_1989 в сообщении #429844 писал(а):

Доказать, что квадрат любого простого числа больше 5 при делении на 30 может дать в остатке только 19 или 1.


если представим простое число как $p=30n+r$
Остаток не может быть кратен 2,3,5, уберем все кратные им, тогда остаются остатки 7, 11, 13, 17, 19, 23, 29.
в нашем случае должно быть$r=1, r=19$

как тогда тут использовать условие что $p>5$?

А чему равны остатки при делении этого квадрата на 2,3 и 5?
Как только поймете - сразу найдете остаток при дел. на 30.

[pb_1989]

$r=1,...,4$ и что?

[ewert]

Да у Вас там и всего-то 7 чисел осталось, просто переберите их квадраты.

pb_1989 в сообщении #429844 писал(а):

как тогда тут использовать условие что $p>5$?

Тут -- никак не использовать. Просто при $p\leqslant5$ получится $n=0$, и эта логика не сработает.

[pb_1989]

Ну да! Квадраты - простые числа. А почему мы будем перебирать их квадраты?
т.е как это объяснить

-- Пт апр 01, 2011 20:25:56 --

хотя наверно правильнее так записать $p^2=30n+r$?

[alex1910]

pb_1989 в сообщении #429851 писал(а):

$r=1,...,4$ и что?

То, что далеко не все перечисленные варианты реализуются.

[Батороев]

Выпишите остатки по основанию $30$ квадратов всех чисел до $30$, а затем вычеркните те, которые не являются взаимнопростыми с числом $30$.

Рассматриваемое в задаче свойство распространяется на большее количество чисел, чем только простые.

[ewert]

pb_1989 в сообщении #429862 писал(а):

А почему мы будем перебирать их квадраты?

Потому, что $(30n+r)^2=900n^2+60nr+r^2$. Вы уже исключили из рассмотрения все $r$, кроме семи штук. Вот и посчитайте остатки от деления на $30$ всех оставшихся семи $r^2$ (больше пары минут для этого точно не потребуется).

[pb_1989]

Да я понимаю, просто мне потом скажут на каком основании вы так делаете. Как это правильно обосновать, интуитивно то понятно, надо ещё грамотно сказать. Т.е среди всех остатков мы исключаем все кратные 30, у нас остается 7 остатков, которые можно перебрирать в принципе.
Почему именно остаток $r^2$ (т.е ост. в квадрате) мы будем делить на 30. Потому что он "неиспользованная часть" данного простого числа?

[ИСН]

Почему 7? И что такое "неиспользованная часть", есть ли в математике такой термин?

[pb_1989]

потому что 7, 11, 13, 17, 19, 23, 29 - 7 чисел

[ИСН]

А 1 уже и не число?

[pb_1989]

число) простые числа сбили с толку

[pb_1989]

a kak тогда обьяснить с 1? её же в квадрат не возведёшь.

[bot]

Дожили - уже и единицу в квадрат возводить нельзя.