упражнения с числами и сравнениями

[vlad_light]

Доказать, что если $x$ и $y$ взаимнопросты с 3, тогда $x^2+y^2$ не является квадратом целого числа.
Подскажите, как начать...

[Praded]

Обозначить, например $x=3n+1, y=3m+2$ и рассмотреть все возможные варианты.

[Joker_vD]

Какие остатки может давать квадрат числа при делении на три? А какие остатки может давать $x^2+y^2$?

UPD. А, ну или так. Но мой способ чуть быстрее.

[vlad_light]

При делении на 3 остача будет $0$ или $1$. А в нашем случае только $1$.
Тогда сумма квадратов может иметь остачу только $2$, а должно быть $0$ или $1$.
Так правильно?

[vlad_light]

Ещё одна задачка:
найти $12^{107} \mathrm {mod} 37$
Как тут действовать? (теории я не знаю )
Могу предположить, что сначала нужно переписать в виде:
$12^{107}=2^{2\cdot 107}\cdot 3^{107}$

[bot]

vlad_light в сообщении #490521 писал(а):

Как тут действовать? (теории я не знаю )

Некоторую теорию надо узнать. Вот слово mod Вам уже знакомо, теперь познакомьтесь с малой теоремой Ферма. Если Вы ещё научитесь находить обратный по модулю, то есть решать сравнения типа $ax\equiv 1 \pmod p$, то эту задачу расколете устно.

[nnosipov]

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

... эту задачу расколете устно

Вот ещё одно устное упражнение на эту же тему: найти последние три цифры числа $1997^{1997}$.

[Sonic86]

vlad_light в сообщении #490521 писал(а):

найти $12^{107} \mathrm {mod} 37$
Как тут действовать? (теории я не знаю )

Теорему Эйлера прочитайте хотя бы:
$\text{НОД}(a,m)=1 \Rightarrow a^{\varphi m} \equiv 1 \pmod m$

upd: формула исправлена

[bot]

Очепятка, должно быть $\text{НОД}(a,m)=1 \Rightarrow a^{\varphi(m)} \equiv 1 \pmod m$, но здесь достаточно частного случая - малой теоремы Ферма, то есть для простого $m$.

[Sonic86]

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

Очепятка, должно быть $\text{НОД}(a,m)=1 \Rightarrow a^{\varphi(m)} \equiv 1 \pmod m$

Угу, исправил.

[vlad_light]

Попробуем
значит, дано $12^{107} (\mathrm{mod} 37)$.
Из т. Ферма можно узнать, что $12^{107\cdot 36}\equiv 1(\mathrm{mod} 37)$
Чтоб найти обратный, нужно решить уравнение $12^{107}x\equiv 1(\mathrm{mod} 37)$.
Тогда $x\equiv(12^{107})^{-1}\equiv(12^{107})^{35}(\mathrm{mod} 37)$.
Обратный нашёл, как дальше действовать?

[nnosipov]

vlad_light, что-то Вы не то делаете, задачка абсолютно устная. Последовательность действий: 1. Применить малую теорему Ферма. 2. Найти обратный. Подсказка: 108 делится на 36.

[vlad_light]

Обратный я правильно нашёл?

(Оффтоп)

Хочу другу подсказку Не понимаю, откуда вытащить 36 и 108. Догадываюсь, что $36=\phi (37)$, насчёт 108 идей нет

[nnosipov]

Да, только он никому не нужен.

-- Вс окт 09, 2011 00:30:08 --

vlad_light в сообщении #490739 писал(а):

насчёт 108 идей нет

$108=107+1$, откуда $107=108-1$.

[vlad_light]

$12^{107}=12^{108}12^{-1}=12^{3\cdot 36}12^{-1}$
$12^{36}\equiv 1 (mod 37)$ - из т. Ферма.
$\Rightarrow (12^{36})^3\equiv 1 (mod 37)$
$\Rightarrow 12^{107}\equiv 12^{-1} (mod 37)$.
Как находить $12^{-1}$?