Hitta det primtiva elementet a (Matematik/Universitet)

Vad är definitionen för ett primitivt element?

Tror att det är en synonym till primitiv rot modulo n.

Du kan snabba upp din sökning genom att logga ordentligt när du löper igenom dina tal och fundera på vad de betyder

2^1 = 2 (mod 23)

2^2 = 4 (mod 23)

2^3 = 8 (mod 23)

2^4 = 16 (mod 23)

2^5 = 9 (mod 23)

2^6 = 18 (mod 23)

2^7 = 13 (mod 23)

2^8 = 3 (mod 23)

2^9 = 6 (mod 23)

2^10 = 12 (mod 23)

2^11 = 1 (mod 23)

Talen som generas av 2 är inte orelaterade till varandra. Ta de som genereras av 3 om du försökte skriva ut dem

3^1 = 3 (mod 23)

3^2 = 9 (mod 23)

3^3 = 4 (mod 23)

3^4 = 12 (mod 23)

3^5 = 13 (mod 23)

3^6 = 16 (mod 23)

3^7 = 2 (mod 23)

3^8 = 6 (mod 23)

3^9 = 18 (mod 23)

3^10 = 8 (mod 23)

3^11 = 1 (mod 23)

Hmmmm... weird. But why?

Smaragdalena skrev:
Vad är definitionen för ett primitivt element?

Smaragdalena skrev:Vad är definitionen för ett primitivt element?
Att om är ett primtivt element så är $a^{p - 1} \equiv 1 (m o d p)$ och att det finns ingen mindre potens än p-1 som är kongruent 1 mod p. Men denna definition säger mig bara att jag måste gå igenom varje potens på a för att se om det finns någon mindre potens än p-1 som är kongruent 1 mod p

SeriousCephalopod skrev:
Du kan snabba upp din sökning genom att logga ordentligt när du löper igenom dina tal och fundera på vad de betyder
2^1 = 2 (mod 23)
2^2 = 4 (mod 23)
2^3 = 8 (mod 23)
2^4 = 16 (mod 23)
2^5 = 9 (mod 23)
2^6 = 18 (mod 23)
2^7 = 13 (mod 23)
2^8 = 3 (mod 23)
2^9 = 6 (mod 23)
2^10 = 12 (mod 23)
2^11 = 1 (mod 23)
Talen som generas av 2 är inte orelaterade till varandra. Ta de som genereras av 3 om du försökte skriva ut dem
3^1 = 3 (mod 23)
3^2 = 9 (mod 23)
3^3 = 4 (mod 23)
3^4 = 12 (mod 23)
3^5 = 13 (mod 23)
3^6 = 16 (mod 23)
3^7 = 2 (mod 23)
3^8 = 6 (mod 23)
3^9 = 18 (mod 23)
3^10 = 8 (mod 23)
3^11 = 1 (mod 23)
Hmmmm... weird. But why?

förstår inte riktigt vad du menar. som sagt när man kommer till potensen 11 verkar det hända något busig.

2^11 = 1 (mod 23)

3^11 = 1 (mod 23)

4^11 = 1 (mod 23)

Det, samt att det är samma tal som förekommer $2^n$ -listan som i $3^n$ -listan där 2 och 3 är gemensamma element. Men dessa listor innehåller ju 11 element. Inte alla 22. (edit) Frågan är om detta är slump eller om det finns någon regel man kan formulera, bevisa, och använda i elementproblemet.

SeriousCephalopod skrev:
Det, samt att det är samma tal som förekommer $2^n$ -listan som i $3^n$ -listan där 2 och 3 är gemensamma element. Men dessa listor innehåller ju 11 element. Inte alla 22. (edit) Frågan är om detta är slump eller om det finns någon regel man kan formulera, bevisa, och använda i elementproblemet.

boken citerar lite kort om "finite fields" men mest bara att dom finns och de används i sammaband med detta så googlade lite och hittade

The order of a finite field must be a prime power. For every prime
power q, there is a field with q elements, and it is unique up to isomorphism

Så betyder då detta då att vi bara behöver kolla primtalen d.v.s. 2,3,5,7... osv

Hur menar du med att kolla primtalen? Primtal som element eller primtal som exponenter? Kan du ge ett exempel på en tillämpning.

Jag skulle väl eg. inte ha så bråttom med att introducera kroppteori [(eng)field = (sv)kropp] när vi än så länge fokusera på gruppegenskaper (endast multiplikation).

Det jag ville till med tabuleringen är att detta indikerar att om $b = 2^k$ för något tal så kan inte $b$ (exempelvis 3) vara ett primitivt element nu när det visat sig att 2 inte är det. Detta kan man härleda genom att utnyttja att potenslagarna $b^{11} = (2^k)^{11} = (2^{11})^k = 1^k = 1$ då detta indikerar att potenssekvensen för alla sådana tal kommer att terminera vid 11 dvs innan 22. Därmed så kan man när man väl löpt igenom 2^k skippa att kolla 3 och 4 då dessa redan uppträtt i 2:s sekvens och hoppa direkt till 5 för att kontrollera den. Om sedan 5 inte visar sig vara ett primitivt element kan man exkludera alla som uppträdde i dess genererade lista och hoppa vidare.

(edit) En bra komplexitets övning kan vara att uppskatta hur snabb en sådan algoritm skulle vara på att hitta alla primitiva element till $Z_p$ för primtal och sedan om man stöter på en annan algoritm kan man jämföra.

SeriousCephalopod skrev:
Hur menar du med att kolla primtalen? Primtal som element eller primtal som exponenter? Kan du ge ett exempel på en tillämpning.
Jag skulle väl eg. inte ha så bråttom med att introducera kroppteori [(eng)field = (sv)kropp] när vi än så länge fokusera på gruppegenskaper (endast multiplikation).
Det jag ville till med tabuleringen är att detta indikerar att om $b = 2^k$ för något tal så kan inte $b$ (exempelvis 3) vara ett primitivt element nu när det visat sig att 2 inte är det. Detta kan man härleda genom att utnyttja att potenslagarna $b^{11} = (2^k)^{11} = (2^{11})^k = 1^k = 1$ då detta indikerar att potenssekvensen för alla sådana tal kommer att terminera vid 11 dvs innan 22. Därmed så kan man när man väl löpt igenom 2^k skippa att kolla 3 och 4 då dessa redan uppträtt i 2:s sekvens och hoppa direkt till 5 för att kontrollera den. Om sedan 5 inte visar sig vara ett primitivt element kan man exkludera alla som uppträdde i dess genererade lista och hoppa vidare.
(edit) En bra komplexitets övning kan vara att uppskatta hur snabb en sådan algoritm skulle vara på att hitta alla primitiva element till $Z_p$ för primtal och sedan om man stöter på en annan algoritm kan man jämföra.

Ok, så vi kan exkludera alla tal som kom med i 2^k sekvensen? eftersom vi fick med 3 och 4 behöver inte kolla dem och går direkt till 5. Men jag förstår inte riktigt hur b^11 = 1 visar att alla tal som kom med i 2^k sekvensen kommer terminera vid 11. jag är helt med på varför det blir 1. men som sagt jag förstår inte varför 2^k tabellen skulle tala om för oss att 3 inte kommer vara ett primitivt element.

Terminerar var kanske fel ord. Sekvensen börjar om där vore nog lämpligare. Så utan att skriva upp 18:s sekvens så vet jag att 18^11 = 1 men därmed är 18^12 = 18 = 18^1 och 18^13 = 18^2 så man går bara runt i en cirkel utan att genera några nya tal och därmed kan de inte vara primtiva element och man behöver inte undersöka dem individuellt.

(edit) Om 3 specifikt så har vi ju från tabellen att 2^8 = 3

Därmed kan man applicera det generiska b-artgumentet på 3 specifikt

$3^{11} = (2^8)^{11} = (2^{11})^8 = 1^8 = 1$

SeriousCephalopod skrev:
Terminerar var kanske fel ord. Sekvensen börjar om där vore nog lämpligare. Så utan att skriva upp 18:s sekvens så vet jag att 18^11 = 1 men därmed är 18^12 = 18 = 18^1 och 18^13 = 18^2 så man går bara runt i en cirkel utan att genera några nya tal och därmed kan de inte vara primtiva element och man behöver inte undersöka dem individuellt.
(edit) Om 3 specifikt så har vi ju från tabellen att 2^8 = 3
Därmed kan man applicera det generiska b-artgumentet på 3 specifikt
$3^{11} = (2^8)^{11} = (2^{11})^8 = 1^8 = 1$

Okej, jag börjar fatta men jag är inte riktigt helt med. Varför börjar så många sekvenser om vid just 11? är det för att 2^11 började om då? Finns det något namn på de här? tänkte något man googla på.

I här fallet formar sekvenserna undergrupper eftersom de innehåller identiteten. Undergrupper till ändliga grupper har alltid ordningar som delar ordningen hos själva gruppen.

Ordningen på gruppen är här 22 så ska du ha undergrupper måste de ha ordning 11 eller 2. Tror det finns ett satsnamn för det. Man kunde nog fått lite mer oförutsägbara relationer om gruppen hade haft fler delare.

Tror jag äntligen förstår, tack!