Теория на числата и сравнения

[Гост]

Здравейте,
ще съм изключително благодарна ако някой може да ми помогне със следните задачи:

1. Кои са последните две цифри на числото 3^8092?

запецнах до 3^40 = 1(мод 100), 8092 = 40х202 + 12 => 3^12 = 1(мод 100) ?
не знам дори дотук така ли е, знам че е малко, но за първи път в живота си виждам подобни задачи, материала не е и преподаден... С мнго ровене във форума стигнах само до това и ще се радвам ако някой може да ми помогне да довърша.

2. Решете системите уравнения
а) х=6 (мод 4)
х=3 (мод 7)
х=10 (мод 9)
пиша със знак равно за по - лесно, иначе си е с трите черти

б) x=2 (mod 11)
x=2 (mod 15)
x= 1 (mod 9)
x=2 (mod 7)

Предварително благодаря за всеки, който ще отдели време )

[ptj]

Достатъчно ти е да знаеш, че остатъците на последователните степени на число по даден модул са циклични. Обяснението е тривиално:

1.) [tex]a^1\equiv a\pmod n[/tex] (за произволни естествени [tex]a,n[/tex])

2.) Ako [tex]a^{p+1}\equiv a \pmod n[/tex], то е вярно и [tex]a^{(p+l)}\equiv a^l \pmod n[/tex] [tex][/tex] (за неотрицателни цели a,p,l,n)

3.) От горните две следва споменатата цикличност, като периода очевидно е някой делител на [tex]p[/tex]

Примери:
Остаците при деление на 10 за степениете на числото 2 са (2,4,8,6), т.е. периода е 4.

Остатъците при деление на 10 за числото 3 са (3,9,7,1), т.е. периода е 4.

Нека се върнем сега на първата задача:

Вече знаем, че [tex]3^{4k}\equiv 1 \pmod {10}[/tex].

Понеже 10 е делител на 100, то ако [tex]3^n\equiv 1 \pmod {100}[/tex] може със сигурност да кажем, че 4 е делител на [tex]n[/tex] (заради горния ред).

Казано по друг начин, ако едно число дава остатък 1 при деление на 100, то естествено то ще дава остатък 1 и при деление на 10.

Тогава остава да намерим най-малкото такова [tex]n[/tex].

Кандидати са 8.12.16,20,...

С непосредствена проверка намираме [tex]3^{20}\equiv 1 \pmod {100}[/tex], т.е. периода е с дължина 20.

[tex]8092\equiv 12 \pmod {20}[/tex]

[tex]3^{8092}\equiv 3^{12} \pmod {100}\equiv 81^3 \pmod{100}\equiv 41 \pmod{100}[/tex] ,

т.е. последните две цифри в десетичния запис на [tex]3^{8092}[/tex] са 41.

[Гост]

Достатъчно ти е да знаеш, че остатъците на последователните степени на число по даден модул са циклични. Обяснението е тривиално:

1.) [tex]a^1\equiv a\pmod n[/tex] (за произволни естествени [tex]a,n[/tex])

2.) Ako [tex]a^{p+1}\equiv a \pmod n[/tex], то е вярно и [tex]a^{(p+l)}\equiv a^l \pmod n[/tex] [tex][/tex] (за неотрицателни цели a,p,l,n)

3.) От горните две следва споменатата цикличност, като периода очевидно е някой делител на [tex]p[/tex]

Примери:
Остаците при деление на 10 за степениете на числото 2 са (2,4,8,6), т.е. периода е 4.

Остатъците при деление на 10 за числото 3 са (3,9,7,1), т.е. периода е 4.

Нека се върнем сега на първата задача:

Вече знаем, че [tex]3^{4k}\equiv 1 \pmod {10}[/tex].

Понеже 10 е делител на 100, то ако [tex]3^n\equiv 1 \pmod {100}[/tex] може със сигурност да кажем, че 4 е делител на [tex]n[/tex] (заради горния ред).

Казано по друг начин, ако едно число дава остатък 1 при деление на 100, то естествено то ще дава остатък 1 и при деление на 10.

Тогава остава да намерим най-малкото такова [tex]n[/tex].

Кандидати са 8.12.16,20,...

С непосредствена проверка намираме [tex]3^{20}\equiv 1 \pmod {100}[/tex], т.е. периода е с дължина 20.

[tex]8092\equiv 12 \pmod {20}[/tex]

[tex]3^{8092}\equiv 3^{12} \pmod {100}\equiv 81^3 \pmod{100}\equiv 41 \pmod{100}[/tex] ,

т.е. последните две цифри в десетичния запис на [tex]3^{8092}[/tex] са 41.

много благодаря