Sistem kongruencija

Sistem kongruencija 02.07.2011. u 14:31 · pre 186 meseci #1

Ja bih molila nekoga da mi pomogne. Naime, radi se o sistemu kongruencija

3x≡11(mod5)
2x≡4(mod7)
10x≡4(mod11)

Eh, iz 3x≡11(mod5) je prof dobila (prije toga je mnozila sa 2) x≡22(mod5) iz cega slijedi da je x≡2(mod5).
Isto tako, iz 10x≡4(mod11) je dobila (prije toga mnozila sa -1) x≡-4(mod11).

Da li mi neko moze objasniti kako je uopste ona dobila tek tako da je x≡22(mod5) pa iz toga dobila x≡2(mod5) i kako je dobila u ovoj drugoj x≡-4(mod11) ?

Ja zaista ne mogu da razumijem na koji nacin se rade sistemi ako se ne krati kao sto je slucaj u drugoj kada se moze odmah kratiti i dijeliti

Hvala svima unaprijed

Re: Sistem kongruencija 02.07.2011. u 14:49 · pre 186 meseci #2

ja mislim da je ovako, neveruj mi na rec, nek neko potvrdi da li je tacno :)

$3x\equiv 11(mod 5) \Leftrightarrow 3x=5k+11, k\in N$
kada pomnozis sa 2 imas $6x=10k+22 \Leftrightarrow 6x\equiv 22(mod 5) \Leftrightarrow 6x\equiv 2(mod 5)$ jer je $22\equiv 2(mod 5)$ i koristis da je $6x\equiv x(mod 5)$ , jer je $6x=5x+x$
ili ovako $6x=10k+22=2k\cdot 5+4\cdot5+2=5\cdot(2k+4)+2 \Leftrightarrow 6x\equiv 2(mod 5)\Leftrightarrow x\equiv 2(mod 5)$

Potpis

Leonardo da Vinči

Nema istine u onim naukama u kojima se matematika ne primenjuje.

Milorad Stevanović

Bog postoji zato sto je matematika neprotivurečna.

Re: Sistem kongruencija 02.07.2011. u 15:39 · pre 186 meseci #3

Celi brojevi $a$ i $b$ su uzajamno prosti akko postoje celi brojevi $m$ i $n$ takvi da je $ma+nb=1$ . U tom slučaju je $ma\equiv_b1$ .

Kako naći brojeve $m$ i $n$ ? Opisaću takozvani prošireni Euklidov algoritam, kojim se pronalaze $m$ i $n$ takvi da je $ma+nb=NZD(a,b)$ .

Kao meru složenosti ovog problema uzećemo veličinu $\max\{|a|,|b|\}$ . Pretpostavimo da je $|a|\geq|b|$ .

1. Ako je $b=0$ , onda je $m=\sgn(a)$ , dok se $n$ može izabrati proizvoljno.

2. Ako je $|b|=1$ , onda se $m$ može izabrati proizvoljno, $n$ se određuje po formuli $n=(1-ma)b$ .

3. Ako je $|b|>1$ , onda najpre treba naći cele brojeve $q$ i $r$ takve da je $a=bq+r$ i $|r|<|b|$ (tzv. delenjem sa ostatkom). Zatim naći cele brojeve $m'$ i $n'$ takve da je $m'b+n'r=NZD(b,r)$ . Ovde treba primetiti da smo polazni problem sveli na problem iste vrste, ali manje složenosti, tako da se na njega primenjuje ista metoda sve dok se ne dođe do jednog od prethodna dva slučaja. Sada treba iskoristiti činjenicu da je $r=a-bq$ i zameniti to u formuli $m'b+n'r=NZD(b,r)$ . Obzirom da je $NZD(a,b)=NZD(b,r)$ , zaključujemo da je $n'(a-bq)+m'b=NZD=(a,b)=n'a+(m'-n'q)$ , odakle sledi da treba uzeti $m=n'$ i $n=m'-n'q$ .

Primer:

Naći cele brojeve $m$ i $n$ takve da je $12m+7n=1$ .

Obzirom da je $12=7+5$ nađimo $m_1$ i $n_1$ takve da je $7m_1+5n_1=1$ i stavimo $m=n_1$ i $n=m_1-n_1q$ .

Obzirom da je $7=5+2$ nađimo $m_2$ i $n_2$ takve da je $5m_2+5n_2=1$ i stavimo $m_1=n_2$ i $n_1=m_2-n_2q$ .

Obzirom da je $5=2\cdot 2+1$ nađimo $m_3$ i $n_3$ takve da je $2m_3+n_3=1$ i stavimo $m_2=n_3$ i $n_2=m_3-2n_3$ .

Recimo,

$m_3=0$ , $n_3=1/tex]; m_2=n_3=1$ , $n_2=m_3-2n_3=-2$ ;
$m_1=n_2=-2$ , $n_1=m_2-n_2=3$ ;
$m=n_1=3$ , $n=m_1-n_1=-5$ ;

Provera: $3\cdot 12-5\cdot 7=36-35=1$ .

E sad, kad imaš kongruenciju $pa\equiv_bq$ sa poznatim $p$ i $q$ i uzajamno prostim $p$ i $b$ , onda najpre treba da nađeš $m$ takvo da je $mp\equiv_b1$ , to jest $m$ i $n$ takve da je $mp+nb=1$ . Zapravo, tebi treba samo $m$ , koga u slučaju malih vrednosti možeš naći običnim pogađanjem. Tada je $a\equiv_bmq$ . Profesorka očigledno ponekad koristi vrednosti $m$ za koje je $mp\equiv_b-1$ , kada je $-a\equiv_bmq$ , odnosno $a\equiv_b-mq$ .

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Re: Sistem kongruencija 02.07.2011. u 15:40 · pre 186 meseci #4

$3x \equiv 11 (mod 5)\Longrightarrow 3x+5y=11$
Sad rijesi $3x+5y=11$ , $(3,5)=1\Longrightarrow 3\cdot 7 +5\cdot(-4)=1$ , $\alpha=7 \land c=11$
$x=\frac{c\cdot \alpha}{d}+{b\cdot t \over d}$
$x_0=\frac{c}{d}\cdot \alpha \Longrightarrow x_0=77$

Provera: $3\cdot77 \equiv 11(mod 5) \Longrightarrow 5|231-11=\frac{220}{5}=q \land q \in Z$

Potpis

حياتي هو العلم بلدي (الرياضيات)

Re: Sistem kongruencija 02.07.2011. u 15:45 · pre 186 meseci #5

@Nedeljko
Mogu li se brojevi $m \land n$ naci prostim Euklidovim algoritmo,mislim ja znam da nadjem jednim Euklidovim algoritmo brojeve $m \land n$ al to nije ovaj koji si ti koristio.

Potpis

حياتي هو العلم بلدي (الرياضيات)

Re: Sistem kongruencija 02.07.2011. u 16:29 · pre 186 meseci #6

Prvo, znak $"\land"$ nije prosta zamena za veznik "i" u Srpskom jeziku, već iskazni logički veznik, koji dakle povezuje iskaze u složeniji iskaz koji je tačan akko su oba sastavka tačna.

Drugo, nisi opisao algoritam koji koristiš, pa ti ne mogu odgovoriti na pitanje.

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Re: Sistem kongruencija 02.07.2011. u 17:32 · pre 186 meseci #7

Evo kako bih nasao u zadatku $3x\equiv_511$
To bi bio ovaj algoritam:
$x=yv_1+r_1$ , $0\le r_1<y$
$y=r_1v_2+r_2$ , $0\le r_2<r_1$
$r_1=r_2v_3+r_3, 0\le r_3<r_2$
$\cdots$ , $\cdots$
$r_{n-2}=r_{n-1}v_n+r_n$ $0\le r_n <r_{n-1}$
$r_{n-1}=r_nv_{n+1}$ .
Imam sad da je $x=5 \land y=3$
$x=yv_1+r_1\Longrightarrow 5=3+2$ ,za $v_1=1 \land r_1=2$
$y=r_1v_2+r_2\Longrightarrow 3=2+1$ ,za $v_2=1 \land r_2=1$
$r_1=r_2v_3+r_3\Longrightarrow 2=1+1$ ,za $v_3=1 \land r_3=1$
Iz cega zakljucejemo da je $(3,5)=1\Longrightarrow 3m+5n=1$
Dalje dobijam: $1=2-1 \Longrightarrow 2(5-3)-3 \Leftrightarrow 2\cdot5-3\cdot3 \Leftrightarrow m=-3,n=2$
I tako bi dobio te brojeve $m$ i $n$ .

Potpis

حياتي هو العلم بلدي (الرياضيات)

Re: Sistem kongruencija 02.07.2011. u 18:29 · pre 186 meseci #8

Koliko vidim, kod tebe je $r_2=r_3=1$ , što nije u skladu sa $r_3<r_2$ . Rekao bih da si ovo hteo da kažeš:

$x=5 \land y=3$
$x=yv_1+r_1\Longrightarrow 5=3+2$ ,za $v_1=1 \land r_1=2$
$y=r_1v_2+r_2\Longrightarrow 3=2+1$ ,za $v_2=1 \land r_2=1$
$r_1=r_2v_3\Longrightarrow 2=2\cdot 1$ ,za $v_3=2$

$1=3-2=3-(5-3)=2\cdot 3-5\Rightarrow m=-1,n=2$ .

Ako je to to, onda bih rekao da se radi o istom algoritmu.

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Re: Sistem kongruencija 02.07.2011. u 18:40 · pre 186 meseci #9

Citat:

Nedeljko:
Rekao bih da si ovo hteo da kažeš:

Da,to sam htio da odradim nego zeznuo sam se u racunu nisam vodio racuna o postvavlejnom uslovu.
I nisam primetio da se radi o istom algoritmu.

Potpis

حياتي هو العلم بلدي (الرياضيات)

Srodne teme