matematikk.net

Boken min forklarer forkorting i kongurenser slik:
1.[tex]c\times ax\equiv c\times b\; (mod\;n)[/tex] og [tex]sfd(c,n)=1[/tex] [tex]\Rightarrow[/tex] [tex] ax\equiv b\; (mod\;n)[/tex]
2.[tex]c\times ax \equiv c\times b\;(mod\;c\times n)\Rightarrow ax\equiv b\;(mod\;n)[/tex]

Men hva hvis: [tex]c\times ax \equiv c\times b\;(mod\;c\times n)[/tex] og [tex]1>sfd(c,n)<c[/tex]

F. eks:
[tex]8448x\equiv 9984\;(mod\;512)[/tex]

Faktorisert:
[tex]11 \times 3 \times 2^{8}\times x\equiv 13 \times 3 \times 2^{8}\;(mod\;2^{9})[/tex]

Har prøvd å først forkorte 2-erpotensen som i eksempel 2 for deretter å forkorte 3-eren som i eksempel 1 og ender da opp med [tex]11x\equiv 13\;(mod\;2)[/tex]. Har jeg gjort det riktig eller jeg på jordet?

Dette ser fint ut dette. Om du har lyst til å sjekke dette selv ser du jo at kongruensen du kom fram til gir at x er kongruent med 1 mod 2, dvs at x er et oddetall. Om x er et partall blir venstresiden i den opprinnelige kongruensen delelig med [tex]2^8 \cdot 2 = 2^9[/tex], og derfor 0 mod [tex]2^9[/tex], mens høyresiden bare har 8 toerfaktorer og derfor ikke er null mod [tex]2^9[/tex]. Men ja, uansett er det du har gjort helt riktig.

Tusen takk! Skjønte ikke hvordan jeg skulle sjekke svaret!

Edit: Hva skjer med [tex]11 \times 2^{8}\times x\equiv 13 \times 2^{8}\;(mod\;2^{8})[/tex]?