Omvendt Fermat

Her kan brukere av forum utfordre hverandre med morsomme oppgaver og nøtter man ønsker å dele med andre. Dette er altså ikke et sted for desperate skrik om hjelp, de kan man poste i de andre forumene, men et sted for problemløsing på tvers av trinn og fag.

Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa

Svar
Gustav
Tyrann
Tyrann
Innlegg: 4555
Registrert: 12/12-2008 12:44

La $p$ være et primtall. Vis at dersom $x^k\equiv 1\pmod p$ for alle $x\not\equiv 0\pmod p$, så vil $p-1$ dele $k$.
Janhaa
Boltzmann
Boltzmann
Innlegg: 8552
Registrert: 21/08-2006 03:46
Sted: Grenland

Gustav skrev:La $p$ være et primtall. Vis at dersom $x^k\equiv 1\pmod p$ for alle $x\not\equiv 0\pmod p$, så vil $p-1$ dele $k$.
her er jeg ikke sikker, men:
har:
[tex]\gcd(k, p-1)[/tex]
der
[tex]d=\gcd(k, p-1)[/tex]
=>
[tex]d=k\cdot u + (p-1)\cdot v[/tex]
u og v er kontanter.
deretter:
[tex]x^d=(x^k)^u\cdot (x^{p-1})^v[/tex]
=>
[tex]x^k=1[/tex]
=>
[tex]x^d=1[/tex]
=>da vil
[tex]d | k[/tex]
og
[tex]p-1 | k[/tex]
?
La verken mennesker eller hendelser ta livsmotet fra deg.
Marie Curie, kjemiker og fysiker.

[tex]\large\dot \rho = -\frac{i}{\hbar}[H,\rho][/tex]
mingjun
Cayley
Cayley
Innlegg: 91
Registrert: 18/11-2016 21:13
Sted: Det projektive planet

Gitt at $ord_p(x)|p-1$ for alle $x\not\equiv 0$, trenger vi kun å vise at det finnes et tall $x$ slik at $ord_p(x)=p-1$. Men gitt at det alltid eksisterer primitive røtter modulo et primtall, er vi ferdige.
Gustav
Tyrann
Tyrann
Innlegg: 4555
Registrert: 12/12-2008 12:44

mingjun skrev:Gitt at $ord_p(x)|p-1$ for alle $x\not\equiv 0$, trenger vi kun å vise at det finnes et tall $x$ slik at $ord_p(x)=p-1$. Men gitt at det alltid eksisterer primitive røtter modulo et primtall, er vi ferdige.
Jepp, hadde en forholdsvis lik løsning: Skriv $k=n(p-1)+d$ der $0\leq d<p-1$. Fra Fermats lille teorem vil $x^k=x^{n(p-1)+d}=(x^{p-1})^n\cdot x^d\equiv x^d\equiv 1$. Anta $d>0$. Siden den multiplikative gruppen $Z_p^{\times}$ er syklisk fins et element $g$ som genererer gruppa, men siden $g^d=1$, så får vi motsigelsen. Dermed må $d=0$ og $k=n(p-1)$, så $p-1|k$.
Svar