КАК СЕ РЕШАВА ??? 2

[v1rusman]

Някой знае ли как се решават следните задачи:
1.Да се намери остатъкът от делението на числото 280^1999 със 17
2.ДА се намерят последните 2 цифри на числото А=1423^161
3.Да се намери двуцифреното число,на което завършва
(12371^56 + 34)^28
4.Да се намери остатъкът от делението на А=2+2^2+2^3+2^4+......+2^1999 с 3
Доколкото съм запознат(а това е съвсем бегло)задачите се решават със сравняване по модул,ама какъв е този метод нз.Помагайте!

[Реклама]

[m1t3]

Това е дял от теорията на числата
числови сравнения.
Сравнение е:
нека А и Б са цели числа, а М е естествено число. Казваме, че А е сравнимо с Б по модул М, ако М дели А-Б. Означава се А≡Б (mod M).

Ето малко свойства на това нещо и ако не се справиш ще ти покажа някоя задача как се решава.

Свойства:
1) a≡a (mod m)
2) AKO a≡b(mod m), TO b≡a (mod m)
3) AKO a≡b(mod m) и b≡c(mod m) => a≡c(mod m)
4) Ако a1≡b1(mod m), a2≡b2(mod m), ... an≡bn(mod m), TO a1 + a2 + .. + an ≡ b1 + b2 + ... bn (mod m)
5) AKO a+b≡c(mod m), TO a≡c-b(mod m)
6) AKO a≡b(mod m), TO a+c≡b+c(mod m)
7) AKO a1≡b1(mod m), a2≡b2(mod m), ... an≡bn(mod m), TO a1.a2...an≡b1.b2...bn(mod m)
8 ) AKO a≡b(mod m) To ac≡bc(mod m)
9) AKO a≡b(mod m) TP aⁿ≡bⁿ(mod m) (n естествено число)
10) AKO a≡b(mod m) и ∫(x) е полином с цели куефицоенто, то ∫(a)≡∫(b) (mod m)

[v1rusman]

Ще може ли да решиш някоя от задачите,за да схвана за какво става въпрос,защото засега изобщо не са ми ясни!

[m1t3]

[m1t3]

Така ето ми го решението на задача
1.Да се намери остатъкът от делението на числото 280^1999 със 17

280²≡13 (mod 17) =>
280¹⁰²⁴≡13 (mod 17)

1999-1024= 975

975 = 3.5².13

280³≡-2 (mod 17) (1)

280⁵≡4 (mod 17) (oт 280≡8 (мод 17) и 280⁴≡13 (мод 17)
=>
280²⁵≡4 (мод 17) (2)

280¹³≡2 (мод 17) (от 280≡8 (мод 17); 280⁴≡13 (мод 17) и 280³≡-2 (мод 17)) (3)

И от (1), (2) и (3) => 280⁹⁷⁵≡4 (мод 17)
Но 280¹⁰²⁴≡13 (мод 17)
и 1024+975=1999 => 280¹⁹⁹⁹≡13+4=17 (мод 17)
или 280¹⁹⁹⁹ се дели точно на 17

ПП : Не съм сигурен дали е вярно обаче

[m1t3]

За задачите където е да се намерят последните 2 цифри е същото като горе самоче търсиш остатъка при деление на 100 (за 2 цифри) на 1000 (за 3) и така нататък

[v1rusman]

Благодаря ти много за решението,въпреки че не разбрах почти нищо Ако някой друг знае как се решават такива задачи,може да ти каже дали решението ти е вярно или не(аз не се наемам )

[Nona]

Отговорът на първа задача е 15.

[v1rusman]

Magi можеш ли да напишеш решението си и да добавиш макар и кратко обяснение ?

[Nona]

[v1rusman]

Много благодаря и на двамата!Вече ми се изясниха "модулите".Magi,тези примери в началото нз как се пише с 3 черти)
41=61(мод 5)
14=-6(мод 4) и т.нт
Тези примери са абсолютно същите като тези,откадето аз взех задачите,а това е някво листче,което ми е дала учителката по математика. Може ли да ми кажеш ти откаде намери теорията за сравненията?

[Nona]

От "Сборник по математика за 8 клас" на Вячеслав Величков и Диана Раковска

[v1rusman]

Този сборник е за извънкласни занимания най-вероятно.Благодаря за информацията!Знаеш ли дали го има и за по-горните класове ?

[Nona]

Сборникът е за свободноизбираема подготовка, но не знам дали има такъв за друг клас освен 8. Аз и този още не съм изрешила, въпреки че сега ще бъда 12 клас

[v1rusman]

Може ли да ми напишеш какви други теми се засягат в този сборник(знам че има за принцип на Дирихле,но само това ),защото мога да си го купя.Да не е от 1999 година на издателство "ЛИК"?
И да те питам за задачата 280^1999 /17
280:17=16(ост => 280=8(мод17)=>280^2=8^2=64=4.17-4=68-4=-4(мод17)
Може ли да се запише не с разлика,а със сбор
280^2=8^2=64=3.17+13=51+13=64=13(мод17),т.е ЗАДЪЛЖИТЕЛНО ли е да изчисляваме винаги с разлика и да получаваме отрицателно число(в случая " -4 " ?

[Nona]

Издателството е "Даниела Убенова", а сборникът е от 2002. Темите, които се включват, са:
1. Логически задачи като необходимо входно ниво
2. Задачи от математически състезания до 7 клас
3. Тържествени преобразувания на дробни алгебрични изрази. Условно тъждества. Доказване на безусловни и условни тъждества и неравенства
4. Приложение на векторите пти решаване на някои геометрични задачи в равнината
5. Математическа индукция
6. Функцията скобка х
7. Принцип на Дирихле
8. Принцип на крайния елемент
9. Сравнения
10. Метод на инвариантите
11. Точки върху 1 права
12. Точки върху 1 окръжност
13. Прави през 1 точка
14. Някои комбинаторни задачи и задачи за оцветяване на точки в равнината
15. Екстремални задачи
16. Задачи от математически състезания и олимпиади

А за задачата - да, може и със сбор

[v1rusman]

Благодаря за ценната информация.Потърсих сборника в интернет,но не мога да го поръчам по интернет,защото го няма никъде!Мислиш ли,че може още да се продава ?

[Nona]

Не знам. Моят го имам от преди 4 години, когато направихме поръчка за целия клас.
Ако това ще ти помогне по някакъв начин, номерът му е:
ISBN 954-791-037-X

[v1rusman]

Със сигурност ще го потърся,защото има интересни теми.Обаче това че от 2002 е кофти,щото може сборникът да не е преиздаван.

[Nona]

За останалите две задачи може да използваш следните теореми:

Малка теорема на Ферма

Ако [tex] \left (a,b \right )=1 [/tex] и [tex] p [/tex] е просто число, то [tex] a^{p-1} \equiv 1 \left ( \bmod p \right ) .[/tex]


Теорема на Ойлер

С [tex] \varphi (n)[/tex] ще означаваме броя на естествените числа, по-малки и взаимнопрости с n. Така определената функция се нарича функция на Ойлер.

Свойства на функцията на Ойлер:
1. Ако [tex] \left (a,b \right )=1 [/tex], то [tex] \varphi (a.b)= \varphi (a) . \varphi (b)[/tex].
2. Aко [tex]n=p^\alpha.q^\mu...r^\nu[/tex], където [tex]p,q,...,r[/tex] са прости числа, то [tex] \varphi (n)=n\left (1-\frac 1p\right )\left (1-\frac 1q\right )...\left (1-\frac 1r\right )[/tex].

Например: [tex] \varphi (560)=\varphi \left( 2^4.5.7\right ) =560\left (1-\frac 12\right )\left (1-\frac 15\right )\left (1-\frac 17\right )=192[/tex].

Ако [tex] \left (a,m \right )=1 [/tex], където [tex]m \in N[/tex] и [tex]a \in Z[/tex], тогава е в сила сравнението [tex]a^{\varphi (m)} \equiv 1\left( \bmod m \right)[/tex]. В частност, ако [tex]m=p[/tex] е просто число, то [tex]\varphi (p)=p-1[/tex] и [tex] a^{p-1} \equiv 1 \left ( \bmod p \right ) [/tex], т.е. малката теорема на Ферма е частен случай на теоремата на Ойлер.

За да намерим последните 2 цифри на числото А=1423¹⁶¹, трябва да намерим остатъка при деление на А със 100 или с други думи да намерим двуцифреното число [tex]\overline {ab}[/tex], такова, че [tex]1423^{161} \equiv \overline {ab} \left ( \bmod 100 \right )[/tex].

(1423, 100)=1, тогава съгласно теоремата на Ойлер [tex]1423^{\varphi (100)} \equiv 1\left( \bmod 100 \right)[/tex].
Но [tex] \varphi (100)=\varphi \left( 2^2.5^2\right ) =2^2.5^2\left (1-\frac 12\right )\left (1-\frac 15\right )=40[/tex].
Тогава [tex]1423^{40} \equiv 1\left( \bmod 100 \right)[/tex].
[tex]1423^{160} \equiv 1\left( \bmod 100 \right)[/tex]
Но [tex]1423 \equiv 23\left( \bmod 100 \right)[/tex]. Следователно
[tex]1423^{161} \equiv 23\left( \bmod 100 \right)[/tex].
Двуцифреното число, на което завършва числото 1423¹⁶¹, е 23.


Трета задача става по същия начин. Опитай да я решиш сам, а ако трябва, ще помагам

[v1rusman]

Спокойно,вече разбрах как се решават!Благодаря много !

[v1rusman]

Май не съм ги разбрал съвсем.... Такъв тип ме затрудняват:
1.Да се намери остатъкът от делението на числото 5438^7 с 9
2.Да се намери остатъкът от делението на числото (1250^196+3)^107 с 97
Ако може ми напиши решенията без да използваш формулите на Ферма и Ойлер,т.е по стандартния начин(благодаря предварително)

[Nona]

5438=9.604+2
[tex]5438\equiv 2 \left( \bmod 9 \right) \\ 5438^7\equiv 2^7 \left( \bmod 9 \right) \\ 2^7=128=14.9+2 \equiv 2 \left( \bmod 9 \right) \\ \Rightarrow 5438^7 \equiv 2 \left( \bmod 9 \right)[/tex]

[tex]-7 \equiv 2 \left( \bmod 9 \right)[/tex]
Събираме двете сравнения и получаваме
[tex]5438^7-7 \equiv 4 \left( \bmod 9 \right)[/tex]
А другата задача не мога да я реша без теоремата на Ойлер

[v1rusman]

Аз съм объркал малко условието:
1.Да се намери остатъкът от делението на 5438^7 - 7 на 9
2.А за 2 - както можеш,то в крайна сметка с теоремата на Ойлер е по-лесно.Трябва да се науча да я използвам.Ако искаш напиши решението си
И последно да питам:Как се доказва делимост от вида:Докажете,че 43^2000-1 се дели на 77 .Може би задачите станаха прекалено много....

[Nona]

За да докажеш, че 43²⁰⁰⁰-1 се дели на 77, трябва да докажеш, че:

[tex]43^{2000}-1\equiv 0 \left ( \bmod 77 \right). [/tex]

A за задачите не се притеснявай. Колкото повече, толкова повече

[Nona]

За да докажем, че едно число се дели на 77, ще докажем, че то се дели на 7 и на 11.

[tex] 43\equiv1\left(\bmod7\right) \\ 43^{2000}\equiv1\left(\bmod7\right)\\-1\equiv6\left(\bmod7\right)\\43^{2000}-1\equiv7\left(\bmod7\right)[/tex]

Следователно 43²⁰⁰⁰-1 се дели на 7.

[tex]43\equiv-1\left(\bmod11\right)\\43^{2000}\equiv1\left(\bmod11\right)\\-1\equiv10\left(\bmod11\right)\\43^{2000}-1\equiv11\left(\bmod11\right)[/tex]

43²⁰⁰⁰-1 се дели и на 11, следователно се дели на 77.

[v1rusman]

Мерси много!Теоремата на Ойлер RuLeZzZ

[Irrefutable]

Ох , програмистка съдба... Ето моето решение на 1-ва