Egenskaper för funktion i Z(4711)

Du kan använda Euklides algoritm! Om du skriver upp alla stegen som leder fram till slutsatsen $\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 $1632$ och $4711$. Mer precist kan du hitta heltalskoefficienter $z,w\in\mathbb{Z}$, sådana att

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

Att göra detta i praktiken och räkna ut fungerande värden på $z$ och $w$ 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]\cdot [z]+[4711]\cdot [w]=[1]\,,$

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

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

dvs. $[1632]$ är inverterbart in $\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!

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

Då kan vi börja undersöka hur vår funktion $f:\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])$.

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

Kan du utifrån detta visa att $[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}:\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 $\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.

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 $ax\equiv b (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?

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]$ i $\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]$ har en multiplikativ invers i $\mathbb{Z}_n$ om och endast om Euklides algoritm ger $\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 $\mathrm{sgd}(1632, 4711)=1$, så $[1632]$ har en multiplikativ invers. Detta räcker för att visa att funktionen $f:\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 $f$ så behöver vi bestämma den multiplikativa inversen för $[1632]$. Med våran extended Euclidean algorithm får vi fram att $-713\cdot 1632 + 247\cdot 4711 = 1$, vilket ger $[-713]\cdot [1632]=[1]$, så tydligen är $[1632]^{-1}=[-713]$.

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

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

Maals skrev:

Jag vet att vi tidigare löst $ax\equiv b (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 $ax\equiv b\,(\mod n)$ kokar också ner till att bestämma $\mathrm{sgd}(a,n)$.

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

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

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

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

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:

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

Vi vill visa att ekvationen

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

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

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

har en lösning för alla $b$, 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 $\mathrm{sgd}(1632,4711)=1$.

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 $Z_{4711}$så är funktionen också det, oavsett konstanten 1792?

Hur skulle det vara utifall vi hade flera variabler t.ex. $f\left(x\right)=x^2+1721x+1066 i Z_{4711}$?
Här kan jag ju inte endast kolla att sgd(1721, 4711)=1 eftersom att jag har en andra variabel $x^2$, eller..?

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 $Z_{4711}$så är funktionen också det, oavsett konstanten 1792?

Precis så är det!

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

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

En sådan translation är alltid inverterbar (eftersom den kan "göras ogjord" genom att subtrahera med $b$) så det som avgör om funktionen $f$ är inverterbar är skalningsfunktionen $g$. Och den är inverterbar om och endast om skalfaktorn $a$ har en multiplikativ invers i $R$.

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:\mathbb{Z}\to\mathbb{Z}$ med $f(x)=2x+5$ är...

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

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

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

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

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

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

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

Maals skrev:

Hur skulle det vara utifall vi hade flera variabler t.ex. $f(x)=x^2+1721x+1066$ i $\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:\mathbb{R}\to\mathbb{R}$ med $f(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+\frac{p}{2})^2-(\frac{p}{4})^2+q$.

Detta kan vi försöka göra med andragradsfunktioner i $\mathbb{Z}_n$ också. Grunden till allt detta är ju till syvene och sist kvadreringsregeln, och den gäller lika bra i $\mathbb{Z}_n$. Det enda problemet är att man får se upp med "division med 2". Om $[2]$ har en multiplikativ invers i $\mathbb{Z}_n$ så är detta inget problem, men för jämna $n$ 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:\mathbb{Z}_{4711}\to\mathbb{Z}_{4711}$ med $f([x])=[x]^2+[1721]\cdot [x]+[1066]$.

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

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

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

  $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]$,

det vill säga

  $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 \Longleftrightarrow ([x]+[3216])^2=[945]\,.$

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

Men hur drar man egentligen roten ur något i $\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]$ inte har några kvadratrötter i $\mathbb{Z}_{4711}$.

Om man jobbar i $\mathbb{Z}_p$ för något primtal $p$ 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\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 $x\in\mathbb{Z}$ sådant att $x^2\equiv 945\,(\mod 4711)$, så måste både $x^2\equiv 945\, (\mod 7)$ och $x^2\equiv 945\,(\mod 673)$ gälla samtidigt. Ser du varför?

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

• För $x^2\equiv 945\, (\mod 7)$ behöver vi inte använda Eulers kriterium, eftersom $945\equiv 0\,(\mod 7)$, så kongruensen lyder helt enkelt $x^2\equiv 0\,(\mod 7)$ som in sin tur är ekvivalent med $x\equiv 0\,(\mod 7)$ och alltså löses av alla multiplar av 7.
• För $x^2\equiv 945\, (\mod 673)$ kan vi enkelt konstatera att $954\equiv 272\,(\mod 673)$ är relativt primt med $673$, och att $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 $x^2\equiv 945\, (\mod 673)$ saknar lösningar.

Från detta drar vi slutsatsen att $[945]$ saknar kvadratrötter i $\mathbb{Z}_{4711}$, och därför också att får andragradsfunktion $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 $\mathbb{Z}_n$ kokar ner till generellt, förutsatt att $[2]$ har en multiplikativ invers så att man lyckas kvadratkomplettera funktionen till formen $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]$.
• Sedan kvadrerar vi.
• Till sist translaterar vi igen: addition med $[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 $\mathbb{Z}_{4711}$ såg vi precis att kvadrering inte är surjektivt, eftersom bland annat elementet $[945]$ saknade kvadratrot. Vi kan också enkelt se att kvadrering misslyckas med att vara injektivt, eftersom $[1]^2=[1]$ samtidigt som $[4710]^2=[1]$.

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

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