Modulär aritmetik, bevis.

Undrar om ett bevis jag formulerat håller, misstänker nämligen att det inte gör det.
Låt Z_m beteckna mängden { [0]_m, [1]_m.......[m-1]_m } och låt vidare Z*_m beteckna delmängden av Z_m som består av alla inverterbara element i Z_m. Satsen säger:

Ifall a ∈ Z*_m så följer att även a^(e) ∈ Z*_m för alla heltal e.

Bevis:
Att a ∈ Z*_m betyder att det finns ett b ∈ Z_m sådant att:

a*b = 1 i Z_m (dvs a^(-1) = b )

Och vi vill visa att även:

a^(e)*b = 1 i Z_m. Vi vet att a*b = 1 i Z_m och om vi upphöjer båda led i e får vi:

(a^(e))*(b^(e)) = 1 i Z_m. Sedan multiplicerar vi båda led med (b)^(e-1) där alltså (b = a^(-1))
Vi erhåller:

a^(e)*b = 1 i Z_m och vi har beviset att a^(e) också har in invers i Z_m således gäller:

a^(e) ∈ Z*_m om a ∈ Z*_m.

Det känns som att något är fel, mest osäker är jag när det gäller användningen av inversen a^(-1). Är beviset godtagbart?

Korrekt.


Nej. Vi vill visa att det finns ett b ∈ Z_m sådant att a^(e)*b = 1 i Z_m.


Tack vare att Z_m är kommutativ/abelsk har du rätt. Annars hade du fått a*b*a*b*...*a*b (e st av var och en av a och b).


Nej. När du multiplicerar båda led av (a^(e))*(b^(e)) = 1 med (b)^(e-1) får du
a^(e)*(b^(2e-1)) = b^(e-1)

e som variabel? Hursomhelst, om a är inverterbart så är a^k inverterbart eftersom a^k = a*a*...*a där ingen av faktorerna är nolldelare. Bygg beviset på det istället.

Hur menar du, "e som variabel?"?

Det är ovanligt att symbolen e används som en variabel.

För heltal är väl n, m, k, i och j vanligare.

I gruppteori (som detta är) brukar e beteckna identitetselementet, dvs det element sådant att a*e = e*a = a för alla a. Därför är det bara förvirrande att använda e som variabel.

Tips: Om a * b = 1, vad blir då a^n * b^n ?

Tack. Dumt misstag.

Gjorde det alldeles för komplicerat för mig, försökte konstruera såväl motsägelsebevs såsom induktionsbevis. Insåg (utan att ha läst ditt tips) att det var så jävla mycket enklare än så.

om a*b = 1 i Z_m och vi upphöjer varje led i e som är ett godtyckligt heltal får vi:

a^(e)*b^(e) = 1 i Z_m. Eftersom b är element av Z_m följer att även b^(e) är ett element av Z_m, kalla b^(e) = u. Vi har alltså:

a^(e)*u = 1 i Z_m för något u element av Z_m. Beviset är klart.

Bra.

Nu var detta som sagt en kommutativ algebra, men om den inte vore det skulle du inte kunna bara upphöja varje led. I det fallet kan man arbeta inifrån i produkten:
a^n * b^n = a^(n-1) * a * b * b^(n-1) = a^(n-1) * 1 * b^(n-1) = a^(n-1) * b^(n-1)
= a^(n-2) * a * b * b^(n-2) = ... = 1

Ovanstående bör ses som idén och för att ge en förståelse för vad som händer. För ett formellt bevis bör man dock använda induktion:
a^0 * b^0 = 1 * 1 = 1
Antag att a^n * b^n = 1. Då gäller a^(n+1) * b^(n+1) = a^n * a * b * b^n = a^n * 1 * b^n
= a^n * b^n = { induktionsantagande } = 1.
Alltså gäller a^n * b^n = 1 för alla n = 0, 1, 2, ...

Hur menar du "formellt bevis"? Är inte detta formellt nog?

Jag har inte börjat med icke-kommutativ algebra.

Det första var inte formellt nog. Med induktionsbevis blir det bättre.