Сравнеия по модулю

[Joker_vD]

Тыры-пыры. Семь в квадрате — сорок девять, приводим по модулю — девять. Семь в кубе — это семь в квадрате (девять) умножить на семь, девятью семь — шестьдесят три, приводим по модулю — три. Семь в четвертой — это семь в кубе (три) умножить на семь, трижды семь — двадцать один, приводим по модулю — один...

[Sverest]

нужно решить такое $49^8 \equiv x (\mod 10)$
по-моему там какие то свойства есть, степеней

[caxap]

caxap в сообщении #460342 писал(а):

Заменяйте числа остатками и всё.

[alex1910]

Вы сначала поймите арифметику остатков, а потом уже ищите "общие свойства", малую теорему Ферма, и.т.д.

Подсказка 49=(-1) (mod 10).

[Sverest]

расскажите про арифметику остатков

[caxap]

Уже была указана одна книга. В гугле можно найти ещё много. В Кванте точно было несколько статей на эту тему. На уровне детского сада всё расписано в книжечке "Математический аквариум".

Заменяйте числа остатками. К этому правилу сводится вся арифметика остатков.

Пример. $14^6\equiv 2^6=4^3\equiv 1^3=1\pmod 3$.

[Батороев]

Sverest в сообщении #460343 писал(а):

НОД$(49;10)=1 $
НОД$(9,10)=1$

НОД можно использовать, но только других чисел, а именно: $\text {НОД}((2-1);(5-1))$

-- 21 июн 2011 11:21 --

(Оффтоп)

А чего мы неверные сравнения решаем?!

-- 21 июн 2011 11:33 --

Хотя, $\text {НОД} (7;10)=1$: $\text {НОД} (9;10)=1$ тоже понадобятся.

[Батороев]

Sverest в сообщении #460393 писал(а):

нужно решить такое $49^8 \equiv x (\mod 10)$
по-моему там какие то свойства есть, степеней

Допустим, число $n=pq$, где $p,q$ - простые числа.
Тогда все числа $a$, взаимнопростые с числом $n$, имеют остаток

$$a^{mb}\equiv 1\pmod {n}$$

где $b=\text {НОД}(p-1;q-1)$, а $m$ - натуральное число.

[Sverest]

alex1910 в сообщении #460400 писал(а):

Вы сначала поймите арифметику остатков, а потом уже ищите "общие свойства", малую теорему Ферма, и.т.д.

Подсказка 49=(-1) (mod 10).

А чем в данном случае 1 отличается от -1, разве нельзя просто 1 записать?

[caxap]

$$...\equiv-21\equiv-11\equiv-1\equiv 9\equiv 19\equiv 29\equiv ...\pmod {10}$$

Может быть вы прочитаете хоть какую-нибудь книжку или статью?