Enkel linær kongurens

[Nebuchadnezzar]

Burde fått til denne oppgaven, litt merkelig..

Er det noen enkle regler på når jeg kan dele på modulusen i en linær kongurens? Eksempelvis

[tex]6x \equiv 15 \pmod{21}[/tex]

Jeg ser at alle leddene her er delelig på 3, men deler jeg tvers gjennom blir jo dette feil...

Prøvde også å løse kongurensen over med regning, men får feil svar. Klarer ikke se hvor feilen min er...
Begynner med å skrive opp den diofantiske likningen

[tex]6x + 15y = 21[/tex]

Ser at fellesnevner er 3, på høyre side. Og at denne deler 21, dermed har vi 3 unike løsninger til kongurensen.

[tex]6\cdot( -2 ) + 15(1) = 3 [/tex]

[tex]6\cdot( -14 ) + 15(7) = 21[/tex]

Herfra tenker jeg at løsningene er gitt som

[tex]x \equiv -14+7t \pmod{21} [/tex]

Men dette ble feil, hvorfor? (Har funger på tidligere oppgaver)

[Vektormannen]

Husk på at [tex]6x \equiv 15 (\text{mod} 21)[/tex] er ekvivalent med at [tex]6x - 15 = 21y[/tex] som gir ligningen [tex]6x - 21y = 15[/tex].

Så jeg tror kanskje du har blandet og satt opp feil ligning?

[Nebuchadnezzar]

Tror det ja. Snart eksamen så dette burde sitte, pinlig at jeg postet i feil forum og...

[Vektormannen]

Du kan godt løse denne på vanlig måte også. Hvis du kan finne en x slik at [tex]6x \equiv 15 (\text{mod} \ 3)[/tex] og [tex]6x \equiv 15 (\text{mod} \ 7)[/tex] så vil det jo gjelde at [tex]6x \equiv 15 (\text{mod} \ 21)[/tex]. Her blir det enkelt, for kongruensen med modulus 3 er jo alltid oppfylt uansett hva x er siden 6 og 15 er delelige på 3. Så i praksis trenger du bare å løse den som er modulo 7.

EDIT: litt kjapp der.

[Nebuchadnezzar]

Leste litt i boka, og virker som en alltid kan dele likningen på gcdèn dersom denne går opp i modulusen. Kanskje det gjør regningen litt enklere for meg ^^
takk for smart tips.

[tex]34x \equiv 60 \pmod{98}[/tex]

Ser at [tex]\gcd(34,60)=2[/tex]

[tex]17x \equiv 30 \pmod{49}[/tex]

Mener i det minste at dette stemmer. Ikke at det bar gjelder for gcd, men i praksis vil jo dette være det største tallet vi kan dele på s.67 1c

[Vektormannen]

Ja, dette stemmer. Jeg kom ikke på det i sted men det blir selvsagt enklere å gjøre det på den måten.

[Nebuchadnezzar]

Finn siste sifferet i [tex]53^{103}[/tex]

[tex]53^{103} \equiv x \pmod{10}[/tex]

Denne var litt vanskelig å løse

Vis at [tex]53^{103}+103^{53}[/tex] er delelig på [tex]39[/tex]

Noen tips?

[Vektormannen]

På den første: Eulers teorem.

Den andre: [tex]53 \equiv 14[/tex] og [tex]103 \equiv -14[/tex] modulo 39. Du får også bruk for Eulers teorem. Det første jeg nevnte trenger du strengt tatt ikke, men det gjør at du kan regne det ut uten å bruke kalkulator for å regne ut store potenser osv.

[Nebuchadnezzar]

Ved å bruke fermat/euler på den første oppnår en vel

[tex] {53^{\varphi \left( {10} \right)}} \equiv 1\left( {\bmod 10} \right) [/tex]

[tex]{\left( {{{53}^4}} \right)^{25}} \equiv {1^{25}}\left( {\bmod 10} \right)[/tex]

[tex] {53^3} \cdot {53^{100}} \equiv {53^3}\left( {\bmod 10} \right) [/tex]

[tex] {53^{103}} \equiv 7\left( {\bmod 10} \right) [/tex]

Så skal jeg se på den andre senere, den gikk jo nærmest opp med hintet ditt. =)

[Vektormannen]

Skal stemme det ja. Jeg vet ikke om du brukte kalkulator eller ikke (du pleier jo å være fan av å gjøre mest mulig for hånd :p) men for å gjøre det for hånd så kan du bruke at [tex]53 \equiv 3[/tex] og dermed få at [tex]53^3 \equiv 3^3 = 27 \equiv 7[/tex] (modulo 10).

Den andre får du sikkert til også.

[Nebuchadnezzar]

Lykke til i morgen mtp bølge =)

[Vektormannen]

Takk

Er IT din første eksamen?

[Nebuchadnezzar]

Tallteori nåkommende mandag?

Code: Select all

2011-12-05 	09:00 	4.00 	Skriftlig 	MA1301 	
2011-12-08 	09:00 	4.00 	Skriftlig 	TDT4105 		
2011-12-13 	09:00 	4.00 	Skriftlig 	MA1101 		
2011-12-16 	09:00 	4.00 	Skriftlig 	FY1001 		
2011-12-20 	09:00 	4.00 	Skriftlig 	MA1201

skrevet på tavlen i hovedbygget, på lesesalen^^ Dere er jo ferdig 16 eller noe med eksamener... Tidlig.. Jaja, sein jul

[Vektormannen]

Haha, kom ikke på at tallteorien er på mandag jeg

Vår siste er i matte 4K som er 19. desember. Så er bare snakk om en dag mindre da.