Как да реша това сравнение

[vanya_pavlova]

[tex]37x\equiv 1(mod 101)[/tex]
колкото и да решавам немога да получа отговор 71 сигурно някъде бъркам-ще се радвам на вашата помощ.

[martin123456]

това сравнение има решение <=> [tex]d=(37,101), d|1[/tex]. това е вярно, понеже [tex]d=1[/tex]. щом [tex]d=1[/tex] значи имаме само 1 решение. непоседствено заместване със 71 сигурно дава решение, значи е то.

[vanya_pavlova]

Ами и аз не мога логиката ми е същата пробвах как ли не имам изпит по "теория на числата" и имам какви ли не материали разучих различни начини за сравнения примера го взех от лекциrте на един професо, в харвард което не е от значение,защото е прост примера и се ядосвам и има и упражнения не мога всички да ги направя,но повечето мога де,но както и да е отговорът е 71 ама проблема е,че не мога да го получа срам голям бера а не искам да я оставям ей така без да съм я разбрала!

[vanya_pavlova]

Ами и аз не мога логиката ми е същата пробвах как ли не имам изпит по "теория на числата" и имам какви ли не материали разучих различни начини за сравнения примера го взех от лекциrте на един професор, в харвард което не е от значение,защото е прост примера и се ядосвам и има и упражнения не мога всички да ги направя,но повечето мога де,но както и да е отговорът е 71 ама проблема е,че не мога да го получа срам голям бера а не искам да я оставям ей така без да съм я разбрала!

[martin123456]

ами в случай на едно решение, аз не знам друг метод освен да се заести с числата от 0,1,2,3,...,100

[vanya_pavlova]

ами в случай на едно решение, аз не знам друг метод освен да се заести с числата от 0,1,2,3,...,100

Благодаря за мнението ,но имам чувството,че някой петокласник ще ме засрами

[indy]

Когато числата са сравнително малки (като тези), често става с "целене".

[tex]37x\equiv 1\,mod 101 \Rightarrow 111 x\equiv 3 \,mod 101 \Rightarrow 10x\equiv 3\, mod 101 \Rightarrow 100x\equiv 30 \,mod 101 \Rightarrow -x\equiv 30 \,mod 101[/tex].

Или [tex]x\equiv -30 mod 101[/tex].
Има естествено и по-научен начин с използване на алгоритъма на Евклид и още по.. с верижни дроби!

[vanya_pavlova]

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

[nikko]

Обаче е много по-добре да се научи и някой метод за решаване. Не е ли така. Единия от ефикасните е чрез използване на следното следствие от алгоритъма на Евклид:
Нека най-големия общ делител на две естествени числа е [tex]d=(a,b)[/tex]. Тогава съществуват единствени цели числа [tex]u,v[/tex] така че [tex]ua+vb=d[/tex].

В конкретния случай когато се решава сревнение от вида [tex]ax+b\equiv 0(\text{mod}\ n)[/tex] се търси представяне на [tex]d=(a,m)[/tex] чрез a и m.
Имаме [tex]a=37,m=101[/tex] и двете са прости числа, следователно са и взаимнопрости. Според теоремата за сравнения от първа степен имаме единствено решение. Използваме алгоритъма на Евклид:
[tex]101=37.2+27[/tex]
[tex]37=27.1+10[/tex]
[tex]27=10.2+7[/tex]
[tex]10=7.1+3[/tex]
[tex]7=3.2+1[/tex]
Сега отпред назад изразяваме остатъците чрез 101 и 37,
[tex]27=101-2.37[/tex]
[tex]10=37-27=37-101+2.37=3.37-101[/tex]
[tex]7=27-2.10=101-2.37-2(3.37-101)=3.101-8.37[/tex]
[tex]3=10-7=3.37-101-(3.101-8.37)=11.37-4.101[/tex]
[tex]1=7-3.2=3.101-8.37-2(11.37-4.101)=11.101-30.37[/tex]
Ако разгледаме последното равенство по модул 101 имаме [tex]-30.37\equiv 1(\text{mod}\ 101)[/tex]
и следователно [tex]-30[/tex] е обратния елемент на 37 по модул 101, умножаваме сравнението с -30 и имаме
[tex]37x\equiv 1(\text{mod}\ 101) \Leftrightarrow -30.37x\equiv -30(\text{mod}\ 101) \Leftrightarrow x\equiv 70(\text{mod}\ 101)[/tex]

[vanya_pavlova]

Nikko и на теб мн благодаря аз вървях по същата логика и стигах до точно този ред от решениетo:

[tex]1=7-3.2=3.101-8.37-2(11.37-4.101)=11.101-30.37[/tex]

и не знаех натам какво да правя числото 11 може би най мн ме бъркаше като,че ли то от толкова решаване и аз вече незнам къде се намирам.....
(bow)

[Станислав]

Може и да постъпиш така [tex]37x\equiv 1(mod 101)\Leftrightarrow 37x\equiv 37^{100} (mod 101)\Leftrightarrow x\equiv 37^{99}(mod 101)[/tex]. Изобщо при [tex]gcd(a,n)=1[/tex], то [tex]a^{-1}\equiv a^{\phi(n)-2}(mod n)[/tex]