Zadanie Wyznacz NWD i kongurencja

Teoria liczb, teoria grafów, indukcja
Otrzymałeś(aś) rozwiązanie do zamieszczonego zadania? - podziękuj autorowi rozwiązania! Kliknij
FoxKantor
Dopiero zaczynam
Dopiero zaczynam
Posty: 17
Rejestracja: 12 cze 2015, 10:03
Podziękowania: 3 razy
Płeć:

Zadanie Wyznacz NWD i kongurencja

Post autor: FoxKantor » 15 cze 2015, 19:52

Witam, pomoże mi ktoś rozwiązać 2 zadanka ? I powiedzieć jak je zrobić :/
1. Niech a= 2024 i b=1610. Wyznczyć NWD(a,b) = d i liczby x,y \(\in\)Z, takie że ac + by= d.
2. Rozwiąza kongurencję 5x=4(mod3) Ile jest rozwiązań x spęłniających nierównosć 0\(\le\)x\(\le\)100.
Będę bardzo wdzięczny :)
Pozdrawiam

irena
Guru
Guru
Posty: 22300
Rejestracja: 10 paź 2009, 19:08
Otrzymane podziękowania: 9841 razy
Płeć:

Post autor: irena » 16 cze 2015, 08:10

1.
\(2024=1610+414\\1610=3\cdot414+368\\414=368+46\\368=8\cdot46+0\)

\(NWD(2024;\ 1610)=46\)

\(46=414-368=414-(1610-3\cdot414)=4\cdot414-1610=4(2024-1610)-1610=4\cdot2024-5\cdot1610\)

\(46=4\cdot2024-5\cdot1610\)

irena
Guru
Guru
Posty: 22300
Rejestracja: 10 paź 2009, 19:08
Otrzymane podziękowania: 9841 razy
Płeć:

Post autor: irena » 16 cze 2015, 08:17

2.
\(5x\equiv4\ (mod\ 3)\\5x\equiv1\ (mod\ 3)\\5x+3y=1\\5\cdot2-3\cdot3=1\\x=2;\ 5;\ 8;\ 11;\ ...\)

\(0\le x\le100\\x=3n-1,\ \ n\in N_+\\x_1=2\\r=3\\x_n=3n-1\le100\\3n\le101\\n\le33,(6)\\n\le33\)

Są 33 takie rozwiązania