|
[quote="filipnet"]Linearna kongruencija nema rjesenje ako M(a,n) ne dijeli b, tj. ako a i
n imaju faktor kojeg b nema. [/quote]
Točno. (uz preciziranje: [i]zajednički[/i] faktor).
[quote]3978 x = 3255 (mod 7361)
3978 = 17*234
7361 = 17*433
3255:17=191, ostatak 8 - dakle 17 ne dijeli 3255
to kuzim![/quote]
Good for you. :-)
[quote]A sta je onda sa 652x= 1111 (mod 2355)
Rjesenje je 1963 (mod 2355)
ali ja tu ne vidim zajednicki faktor?[/quote]
...Što je potpuno konzistentno s ovim gore. Evo još jednom: linearna kongruencija nema rješenje ako (infact, "akko" - tj, ako i samo ako) NZM(a,n) ne dijeli b . Dakle, po kontrapoziciji, ako NZM(a,n) _dijeli_ b , tada linearna kongruencija a x==b(mod n) _ima_ rješenje.
Lako se vidi (Euklidov algoritam) da je NZM(652,2355)=1 , a 1 očito dijeli 1111 . Dakle, ta kongruencija ima rješenje (koje se BTW dobije množeći čitavu kongruenciju s inverzom od 652 modulo 2355 - koji postoji _upravo zato_ što je 652 relativno prost s 2355 , i koji se dobije iz istog tog Euklidovog algoritma, pomoću back-supstitucije ili famozne tablice).
I tvoja druga rečenica je točna: "...ako a i n imaju (zajednički) faktor kojeg b nema." Činjenica je da 652 i 2355 uopće nemaju _ikakvih_ zajedničkih faktora (osim 1 ), pa onda pogotovo nemaju takvih kakve 1111 nema.
Sve jasno?
Savjet: ponovi si malo zašto je univerzalna kvantifikacija po praznom skupu uvijek istinita - moglo bi ti zatrebati i u drugim zadacima...
| filipnet (napisa): | Linearna kongruencija nema rjesenje ako M(a,n) ne dijeli b, tj. ako a i
n imaju faktor kojeg b nema. |
Točno. (uz preciziranje: zajednički faktor).
| Citat: | 3978 x = 3255 (mod 7361)
3978 = 17*234
7361 = 17*433
3255:17=191, ostatak 8 - dakle 17 ne dijeli 3255
to kuzim! |
Good for you. 
| Citat: | A sta je onda sa 652x= 1111 (mod 2355)
Rjesenje je 1963 (mod 2355)
ali ja tu ne vidim zajednicki faktor? |
...Što je potpuno konzistentno s ovim gore. Evo još jednom: linearna kongruencija nema rješenje ako (infact, "akko" - tj, ako i samo ako) NZM(a,n) ne dijeli b . Dakle, po kontrapoziciji, ako NZM(a,n) _dijeli_ b , tada linearna kongruencija a x==b(mod n) _ima_ rješenje.
Lako se vidi (Euklidov algoritam) da je NZM(652,2355)=1 , a 1 očito dijeli 1111 . Dakle, ta kongruencija ima rješenje (koje se BTW dobije množeći čitavu kongruenciju s inverzom od 652 modulo 2355 - koji postoji _upravo zato_ što je 652 relativno prost s 2355 , i koji se dobije iz istog tog Euklidovog algoritma, pomoću back-supstitucije ili famozne tablice).
I tvoja druga rečenica je točna: "...ako a i n imaju (zajednički) faktor kojeg b nema." Činjenica je da 652 i 2355 uopće nemaju _ikakvih_ zajedničkih faktora (osim 1 ), pa onda pogotovo nemaju takvih kakve 1111 nema.
Sve jasno?
Savjet: ponovi si malo zašto je univerzalna kvantifikacija po praznom skupu uvijek istinita - moglo bi ti zatrebati i u drugim zadacima...
|
