Citat:
Ursprungligen postat av
melyhna
Finn en lösning till ekvationen
3=x^{29} i Z(184)
detta ska tydligt va eulers sats(?): x^{fi(n)} = 1 i Z(n)
n i vårt fall är 29 eller 184?!
eller ska man använda Euklides algortim?? Bak och framlänges?
184 = q*29+r
som man ställerupp va?
Eulers kräver ju att x och n har största gemensam delare lika med ett. Låt oss anta att det stämmer och kolla när vi får svaret?
Man behöver fi(184), det finns en formel på wiki, den ser ut så här:
fi(n) = n*(1 - (1/p1))*(1-(1/p2))*... tills alla primtal som ingår i n:s faktorisering finns med.
n = 184 = 92*2 = 46*4 = 23*8 = 23* 2^3 Så 23 och 2 är primisarna --->
fi(n) = 184 ( 1 -(1/23))*(1-(1/2)) = 184* (22/23) *(1/2) = 88 Kontrollera så jag inte dummat mig!
x^88 = 1 (mod 184) Nu kan man köra det du föreslog tror jag 88 = 1 +29*3 så:
x^88 = x^29 * x^29 * x^29 * x = 1 (mod 184), men x^29 vet vi är 3---->
9*x = 1 (mod 184) nu gäller det att hitta inversen för 9
Den får jag till 75(kolla själv!) 75 kan primtalsfaktoriseras till 5*5*3 och då var antagandet om gcd ok,
då n = 23*2^3