9 svar
115 visningar
Maals är nöjd med hjälpen
Maals 82
Postad: 17 sep 2020 17:30 Redigerad: 3 okt 2020 19:14

Egenskaper för funktion i Z(4711)

Jag har försökt tolka facit på denna uppgiften men försöker förstå varför man tar sgd(1632, 4711) = 1

och på så sätt kan säga att 1632 är inverterbar i Z4711

Vad säger största gemensamma nämnaren mellan mod 4711 och 1632 om funktionens inverterbarhet?

Flyttade tråden från Ma5 till ma/Uni /Smaragdalena, moderator

oggih 871 – F.d. Moderator
Postad: 17 sep 2020 17:46 Redigerad: 17 sep 2020 18:07

Du kan använda Euklides algoritm! Om du skriver upp alla stegen som leder fram till slutsatsen sgd(1632,4711)=1\mathrm{sgd}(1632,4711)=1, så kan du genom att subsitituera och jobba "baklänges" uttrycka den största gemensamma delaren som en linjärkombination av 16321632 och 47114711. Mer precist kan du hitta heltalskoefficienter z,wz,w\in\mathbb{Z}, sådana att

   1632z+4711w=1.1632z+4711w=1\,.

Att göra detta i praktiken och räkna ut fungerande värden på zz och ww kan vara lite bökigt och tidsödande, men ofta (till exempel i det här fallet) kommer man undan med att veta att det går*.

Mod 4711 ger likheten ovan nämligen attt

  [1632]·[z]+[4711]·[w]=[1],[1632]\cdot [z]+[4711]\cdot [w]=[1]\,,

men [4711]=[0][4711]=[0], så vi får

   [1632]·[z]=[1],[1632]\cdot [z]=[1]\,,

dvs. [1632][1632] är inverterbart in Z4711\mathbb{Z}_{4711}.

* Detta faktum är faktiskt så användbart att man har gett det namnet Bézouts identitet. Ni har kanske redan gått igenom detta i din kurs - annars kommer du säkert stöta på det om du läser mer talteori efter gymnasiet!

oggih 871 – F.d. Moderator
Postad: 17 sep 2020 18:03 Redigerad: 17 sep 2020 18:12

Nu vet vi att [1631][1631] har en multiplikativ invers i Z4711\mathbb{Z}_{4711}. Om vi vill kan vi fortsätta kalla den [z][z], eller så införa vi den mer praktiska symbolen [1631]-1[1631]^{-1}.

Då kan vi börja undersöka hur vår funktion f:Z4711Z4711f:\mathbb{Z}_{4711}\to \mathbb{Z}_{4711} fungerar.

Låt oss börja med att kolla injektivitet. Det klassiska sättet att visa detta på är att anta att två inputs ger samma output, och sedan visa att den enda möjligheten då är att dessa inputs var lika med varandra.

Vi antar med andra ord att f([x])=f([y])f([x])=f([y]).

Det innebär att [1632]·[x]+[1792]=[1632]·[y]+[1792][1632]\cdot [x]+[1792]=[1632]\cdot [y]+[1792].

Kan du utifrån detta visa att [x]=[y][x]=[y] måste gälla?

När du har klarat detta kan du gå vidare och visa surjektivitet.

Kanske kan du till och med hitta en explicit invers f-1:Z4711Z4711f^{-1}:\mathbb{Z}_{4711}\to\mathbb{Z}_{4711}?

Om du kör fast är det bara att säga till, så hjälper jag eller någon annan här gärna dig vidare!

Sidenote: Jag använder hakparenteser för att indikera att vi jobbar i talsystemet Z4711\mathbb{Z}_{4711} i stället för de vanliga heltalen \mathbb{Z}. Om detta känns som en förvirrande notation kan du bara ignorera hakparentserna.

Maals 82
Postad: 17 sep 2020 18:31

Jag följer typ med på vad du säger utöver det första (haha)

Hur förstår jag att jag ska kolla på sgd(1632, 4711) (jag hade alltså sett detta från facit), detta är första gången jag ser moduloräkning i en funktion.

 

Jag vet att vi tidigare löst axb (mod n) genom att skriva om till  ax-ny=b och sedan gjort Euklides osv.

har det NÅGOT med detta att göra? 

 

Vi har jobbat med Bezouts identitet, tror våran lärare kallade den extended euclidean algorithm, men det verkar inte som att du använder den för att lösa denna uppgift alls?

oggih 871 – F.d. Moderator
Postad: 19 sep 2020 11:58 Redigerad: 19 sep 2020 12:01

Om man börjar med att fundera på vad injektivitet, surjektivitet och inverterbarhet innebär (ungefär så som jag gjorde i mitt andra inlägg här ovan), så inser man ganska snabbt att detta kokar ner till inverterbarhet av [1632][1632] i Z4711\mathbb{Z}_{4711}.

Det klassiska sättet att kolla om en sådan multiplikativ invers finns - och vid behov beräkna den - är just med Euklides algoritm. Generellt gäller att [a][a] har en multiplikativ invers i Zn\mathbb{Z}_n om och endast om Euklides algoritm ger sgd(a,n)=1\mathrm{sgd}(a,n)=1, och vill vi hitta inversen kan vi använda the extended Euclidean algoritm (det jag kallar "arbeta baklänges") för att hitta inversen.

I detta falllet gäller sgd(1632,4711)=1\mathrm{sgd}(1632, 4711)=1, så [1632][1632] har en multiplikativ invers. Detta räcker för att visa att funktionen f:Z4711Z4711f:\mathbb{Z}_{4711}\to\mathbb{Z}_{4711} är både injektiv och surjektiv, och därmed även inverterbar. (Säg till om du behöver hjälp med att visa detta!)

Men - om vi vill hitta en explicit invers till funktionen ff så behöver vi bestämma den multiplikativa inversen för [1632][1632]. Med våran extended Euclidean algorithm får vi fram att -713·1632+247·4711=1-713\cdot 1632 + 247\cdot 4711 = 1, vilket ger [-713]·[1632]=[1][-713]\cdot [1632]=[1], så tydligen är [1632]-1=[-713][1632]^{-1}=[-713].

(Tycker vi negativa tal är jobbigt kan vi så klart addera med 47114711, så ar tt vi i stället får [1632]-1=[3998][1632]^{-1}=[3998].)

Hjälpte detta? Ser du vad inversen till funktionen ff blir nu? ^_^

oggih 871 – F.d. Moderator
Postad: 19 sep 2020 12:32 Redigerad: 19 sep 2020 12:36
Maals skrev:

Jag vet att vi tidigare löst axb (mod n) genom att skriva om till  ax-ny=b och sedan gjort Euklides osv.
har det NÅGOT med detta att göra? 

Ohja! Att lösa ekvationen axb(modn)ax\equiv b\,(\mod n) kokar också ner till att bestämma sgd(a,n)\mathrm{sgd}(a,n).

Tricket är precis som du skriver att notera att axb(modn)ax\equiv b\,(\mod n) gäller om och endast om ax-b=nyax-b=ny för något yy\in\mathbb{Z}, dvs. om och endast om den diofantiska ekvationen ax-ny=bax-ny=b har lösningar. Och som du säkert vet har den det om och endast om bb är en multipel av sgd(a,n)\mathrm{sgd}(a,n), och vill man hitta lösningarna kan man använda Euklides baklänges!

Notera speciellt att detta innebär att axb(modn)ax\equiv b\,(\mod n) är lösbar för alla högerled bb\in\mathbb{Z} om och endast om sgd(a,n)=1\mathrm{sgd}(a,n)=1. (Vilket är ekvivalent med att [a][a] har en multiplikativ invers i Zn\mathbb{Z}_n.)


Om vi vill så skulle vi  kunna använda detta för att visa att vår funktion f:Z4711Z4711f:\mathbb{Z}_{4711}\to \mathbb{Z}_{4711} är surjektiv.

Det vi behöver visa är att för varje [b]Z4711[b]\in\mathbb{Z}_{4711} så finns det ett [x]Z4711[x]\in \mathbb{Z}_{4711} sådant att f([x])=[b]f([x])=[b], dvs. vi behöver visa att ekvationen [1632]·[x]+[1792]=[b][1632]\cdot [x]+[1792]=[b]har en lösning för alla bb

Jag skulle resoenera på följande sätt, utan att explicit referera till kongruenser eller det vi sa här ovanför om diofantiska ekvationer:

Visa spoiler

Eftersom vi vet att sgd(1632,4711)=1\mathrm{sgd}(1632,4711)=1 och att [1632][1632] därför har en multiplikativ invers, så är detta enkelt. Det vanliga ekvationslösningstänktet från högstadiet ger   

   [1632]·[x]=[b]-[1792][1632]\cdot [x]=[b]-[1792] 

   [x]=[1632]-1([b]-[1792]),[x]=[1632]^{-1}([b]-[1792])\,,

dvs. det finns en lösning!

Men om man gillar kongruenstecken och diofantiska ekvationer kan man i stället uttrycka sig så här:

Vi vill visa att ekvationen

   1632x+1792b(mod4711)1632x+1792\equiv b\,(\mod 4711)

har en lösning för alla bb, eller, ekvivalent, att ekvationen

   1632xb-1792(mod4711)1632x\equiv b-1792\,(\mod 4711)

har en lösning för alla bb, dvs. för alla möjliga värden av högerledet.

Och det har den ju (om vi följer resonemanget i början av inlägget), just eftersom sgd(1632,4711)=1\mathrm{sgd}(1632,4711)=1.

Maals 82
Postad: 19 sep 2020 19:36

Vill tacka för dina grymma svar!

Om jag förstått det hela rätt så är det viktiga att kolla på variabelns koefficient, alltså 1632 och om den är inverterar i Z4711så är funktionen också det, oavsett konstanten 1792?

 

Hur skulle det vara utifall vi hade flera variabler t.ex. f(x)=x2+1721x+1066     i Z4711?
Här kan jag ju inte endast kolla att sgd(1721, 4711)=1 eftersom att jag har en andra variabel x2, eller..?

oggih 871 – F.d. Moderator
Postad: 20 sep 2020 12:45 Redigerad: 20 sep 2020 12:45
Maals skrev:

Om jag förstått det hela rätt så är det viktiga att kolla på variabelns koefficient, alltså 1632 och om den är inverterar i Z4711så är funktionen också det, oavsett konstanten 1792?

Precis så är det!

Man kan se det som att en funktion f:RRf:R\to R (där RR är vilken så kallad ring som helst, t.ex. \mathbb{Z}, \mathbb{R} ellöer Zn\mathbb{Z}_n) på formen f(x)=ax+bf(x)=ax+b är en sammansättning av två "delfunktioner":

  • Först gör vi en skalning: g:RRg:R\to R med g(x)=axg(x)=ax.
  • Sedan gör vi en translation: h:RRh:R\to R med h(y)=y+bh(y)=y+b.

En sådan translation är alltid inverterbar (eftersom den kan "göras ogjord" genom att subtrahera med bb) så det som avgör om funktionen ff är inverterbar är skalningsfunktionen gg. Och den är inverterbar om och endast om skalfaktorn aa har en multiplikativ invers i RR.


Några exempel på detta (skissa gärna graferna, så att du får en känsla för hur de ser ut!):

Funktionen f:f:\mathbb{Z}\to\mathbb{Z} med f(x)=2x+5f(x)=2x+5 är...

Visa spoiler...inte inverterbar, eftersom det inte finns någon multiplikativ invers till skalfaktorn 2 i \mathbb{Z}. (Den här funktionen missar alla jämna tal i målmängden, så den är inte surjektiv!)

Funktionen f:f:\mathbb{Z}\to\mathbb{Z} med f(x)=-x+8f(x)=-x+8 är...

Visa spoiler...däremot inverterbar, eftersom skalfaktorn (-1)(-1) har sig själv som multiplikativ invers.

Funktionen f:f:\mathbb{Q}\to\mathbb{Q} med f(x)=2x+5f(x)=2x+5 är...

Visa spoiler...också inverterbar, eftersom skalfaktorn 2 har en multiplikativ invers i \mathbb{Q}.

Funktionen f:Z6Z6f:\mathbb{Z}_6\to\mathbb{Z}_6 med f([x])=[2]·[x]+[5]f([x])=[2]\cdot [x]+[5] är...

Visa spoiler...inte inverterbar, eftersom skalfaktorn [2][2] saknar multiplikativ invers i Z6\mathbb{Z}_6. (Om man inte ser det direkt så kan man se det genom att sgd(2,6)=21\mathrm{sgd}(2,6)=2\neq 1.)

Speciellt är den här funktionen inte surjektiv, eftersom den bara träffar elementen [1][1], [3][3] och [5][5] i målmängden.

Den är inte heller injektiv, eftersom bland annat f([0])=[5]=f([3])f([0])=[5]=f([3]).

Funktionen f:Z7Z7f:\mathbb{Z}_7\to\mathbb{Z}_7 med f([x])=[2]·[x]+[5]f([x])=[2]\cdot [x]+[5] är...

Visa spoiler...inverterbar, eftersom skalfaktorn [2][2] har en multiplikativ invers i Z7\mathbb{Z}_7. (Detta kan vi återigen se med Euklides algoritm, som även talar om att inversen är [4][4], om vi inte såg det direkt.)

En följdfråga om du vill fundera mer på detta:

Kan du ge ett förslag på en skalfaktor [a]Z4711[a]\in\mathbb{Z}_{4711} som inte ger inverterbar funktion Z4711Z4711\mathbb{Z}_{4711}\to\mathbb{Z}_{4711}?

Smaragdalena 54128 – Lärare
Postad: 20 sep 2020 13:17

Är detta verkligen Ma5? Det liknar ingenting som finns i den Ma5-bok som jag använder. /moderator

oggih 871 – F.d. Moderator
Postad: 20 sep 2020 16:26 Redigerad: 21 sep 2020 23:52
Maals skrev:

Hur skulle det vara utifall vi hade flera variabler t.ex. f(x)=x2+1721x+1066f(x)=x^2+1721x+1066 i Z4711\mathbb{Z}_{4711}?

En utmärkt fråga! ^_^

Tyvärr har talteori aldrig varit min starkaste sida, så jag kommer nog inte kunna göra detta full rättvisa eller förklara det på något superpedagogiskt sätt, utan vi får hoppas att någon annan här på forumet har bättre koll och kan hoppa in och hjälpa oss!

Men tills dess kan jag säga följande: 

När vi lärde oss hantera andragradsfunktioner i Matematik 2 var tricket att kvadratkomplettera. Har vi en funktion f:f:\mathbb{R}\to\mathbb{R} med f(x)=x2+px+qf(x)=x^2+px+q så är det mycket enklare att dra slutsatser om hur den kommer bete sig om vi skriver om den till

   f(x)=(x+p2)2-(p4)2+qf(x)=(x+\frac{p}{2})^2-(\frac{p}{4})^2+q.

Detta kan vi försöka göra med andragradsfunktioner i Zn\mathbb{Z}_n också. Grunden till allt detta är ju till syvene och sist kvadreringsregeln, och den gäller lika bra i Zn\mathbb{Z}_n. Det enda problemet är att man får se upp med "division med 2". Om [2][2] har en multiplikativ invers i Zn\mathbb{Z}_n så är detta inget problem, men för jämna nn kommer detta inte fungera, och då är man hänvisad till andra metoder... 

Vi bortser för stunden även från att det kan finnas koefficienter framför andragradstermen.


Låt oss prova att kvadratkomplettera i ditt exempel: f:Z4711Z4711f:\mathbb{Z}_{4711}\to\mathbb{Z}_{4711} med f([x])=[x]2+[1721]·[x]+[1066]f([x])=[x]^2+[1721]\cdot [x]+[1066].

Vi börjar med att konstatera att den multiplikativa inversen till [2][2] är [2356][2356] (detta kan du komma fram till med Euklides algoritm). Vi får nu att motsvarigheten till p/2p/2 blir [1721]·[2356]=[3216][1721]\cdot [2356]=[3216]. Alltså gäller

   f([x])=[x]2+[2]·[3216]·[x]+[1066]f([x])=[x]^2+[2]\cdot [3216]\cdot [x]+[1066].

Motsvarigheten till (p/2)2(p/2)^2 blir [3216]2=2011[3216]^2=2011, så vi kan skriva

  f([x])=[x]2+[2]·[3216]·[x]+[2011]-[2011]+[1066]f([x])=[x]^2+[2]\cdot [3216]\cdot [x]+[2011]-[2011]+[1066],

vilket med kvadreringsregeln baklänges ger

  f([x])=([x]+[3216])2-[2011]+[1066]f([x])=([x]+[3216])^2-[2011]+[1066],

det vill säga

  f([x])=([x]+[3216])2-[945]f([x])=([x]+[3216])^2-[945].


Detta är användbart på många sätt. Vill vi till exempel kolla om funktionen har några nollställen, så får vi ekvationen

   ([x]+[3216])2-[945]=0([x]+[3216])2=[945].([x]+[3216])^2-[945]=0 \Longleftrightarrow ([x]+[3216])^2=[945]\,.

Det betyder att vi får en lösning [x]=-[3216]+[r][x]=-[3216]+[r], för varje kvadratrot [r][r] av [945][945] (varje element [r]Z4711[r]\in\mathbb {Z}_{4711} sådant att [r]2=[945][r]^2=[945]).

Men hur drar man egentligen roten ur något i Zn\mathbb{Z}_n? Det är dessvärre en lång historia, som jag inte behärskar till fullo, men några nyckelord är kinesiska restsatsen, Lagrange-symboler och kvadratiska rester (eng. quadratic residues), som någon annan gärna får redogöra mer utförligt för.

Men det jag kan göra är att (försöka) förklara hur man kan komma fram till att [945][945] inte har några kvadratrötter i Z4711\mathbb{Z}_{4711}.

Om man jobbar i Zp\mathbb{Z}_p för något primtal pp så kan man undersöka huruvida det finns några kvadratrötter med något som kallas för Eulers kriterium, men tyvärr är 4711=7·6734711=7\cdot 673 inget primtal...

Lyckligtvis visar det sig dock att man kan analysera varje primtalsfaktor för sig (men om vi har fler än en primtalsfaktor av samma sort blir det stökigare). Det gäller nämligen att om det finns xx\in\mathbb{Z} sådant att x2945(mod4711)x^2\equiv 945\,(\mod 4711), så måste både x2945(mod7)x^2\equiv 945\, (\mod 7) och x2945(mod673)x^2\equiv 945\,(\mod 673) gälla samtidigt. Ser du varför?

Visa spoiler

Låt pp och qq vara primtal sådana att ab(modpq)a\equiv b\,(\mod pq). Detta är ekvivalent med att pq(a-b)pq\mid (a-b) vilket i sin tur är ekvivalent med att p(a-b)p\mid (a-b) och q(a-b)q\mid (a-b), dvs. ab(modp)a\equiv b\,(\mod p) och ab(modq)a\equiv b\,(\mod q).

Låt oss nu studera dessa båda kongruenser var för sig:

  • För x2945(mod7)x^2\equiv 945\, (\mod 7) behöver vi inte använda Eulers kriterium, eftersom 9450(mod7)945\equiv 0\,(\mod 7), så kongruensen lyder helt enkelt x20(mod7)x^2\equiv 0\,(\mod 7) som in sin tur är ekvivalent med x0(mod7)x\equiv 0\,(\mod 7) och alltså löses av alla multiplar av 7.
  • För x2945(mod673)x^2\equiv 945\, (\mod 673) kan vi enkelt konstatera att 954272(mod673)954\equiv 272\,(\mod 673) är relativt primt med 673673, och att 272(673-1)/2-1(mod673)272^{(673-1)/2}\equiv -1\,(\mod 673) (här får man nog använda en miniräknare!), vilket enligt Eulers kriterium betyder att x2945(mod673)x^2\equiv 945\, (\mod 673) saknar lösningar.

Från detta drar vi slutsatsen att [945][945] saknar kvadratrötter i Z4711\mathbb{Z}_{4711}, och därför också att får andragradsfunktion f([x])=([x]+[3216])2-[945]f([x])=([x]+[3216])^2-[945] saknar nollställen. Speciellt betyder detta att funktionen inte är surjektiv, och att den därför inte heller kan vara inverterbar.


Och det är precis detta som inverterbarhet för andragradare i en generell ring Zn\mathbb{Z}_n kokar ner till generellt, förutsatt att [2][2] har en multiplikativ invers så att man lyckas kvadratkomplettera funktionen till formen f([x])=([x]+[b])2+[c]f([x])=([x]+[b])^2+[c]. Då kan funktionen precis som innan delas upp i delfunktioner:

  • Först utför vi en translation: addition med [b][b].
  • Sedan kvadrerar vi.
  • Till sist translaterar vi igen: addition med [c][c].

Eftersom translationerna så klart är inverterbara, så hänger allt kvadreringen. Om kvadrering är injektivt i ringen vi jobbar i, så blir alla kvadratkompletterbara andragradare injektiva; om kvadreringen är surjektivt i ringen vi jobbar i, så blir alla kvadratkompletteringsbara andragradare surjektiva.

I Z4711\mathbb{Z}_{4711} såg vi precis att kvadrering inte är surjektivt, eftersom bland annat elementet [945][945] saknade kvadratrot. Vi kan också enkelt se att kvadrering misslyckas med att vara injektivt, eftersom [1]2=[1][1]^2=[1] samtidigt som [4710]2=[1][4710]^2=[1].

(Detta gäller för övigt även generellt: Kvadrering misslyckas alltid med att vara injektivt i Zn\mathbb{Z}_n för alla nn utom 2, eftersom det då gäller att [1][n-1][1]\neq [n-1], men likväl att [1]2=[1][1]^2=[1] och [n-1]2=[-1]2=[1][n-1]^2=[-1]^2=[1].)

Strök (på Oggihs uppmaning) bort några ord som inte borde vara där /Smaragdalena, moderator

Svara Avbryt
Close