Guidning i modulo-ekvationer

Hej allesammans!

Jag undrar om någon hade kunnat ge mig en nickning i rätt riktning gällande dessa två uppgifter?

1. Bestäm resten då talet 18! divideras med 37.

2. Bestäm heltalet A, 1 ≤ 𝐴 ≤ 20, så att 𝐴 ≡ 20! (𝑚𝑜𝑑 23)

Ska man använda sig av Wilsons sats för båda dessa uppgifter? Detta trots att det känns som att det blir en lång uppställning/uträkning i uppgift 1, eftersom 18 ligger rätt långt ifrån 36 (aka p-1)?

Man kan utnyttja Wilsons sats i båda uppgifterna. (Jag har dock ingen aning om det är den optimala vägen till att lösa uppgifterna.)

2. Enligt Wilsons sats är $22! \equiv -1 (\mod 23)$ .

Det gäller att $22! = 20! \cdot 21 \cdot 22$ . Dessutom är $21 \equiv -2 (\mod 23)$ samt $22 \equiv -1 (\mod 23)$ .

Visa spoiler

Därmed är $20! \cdot (-2) \cdot (-1) \equiv -1 (\mod 23)$ och därmed $20! \cdot 2 \equiv 22 (\mod 23)$ .

1. Enligt Wilsons sats är $36! \equiv -1 (\mod 37)$ . Man kan utnyttja liknande knep här, nämligen

$19\equiv -18$ ,
$20 \equiv -17$
$21 \equiv -16$
...
$36 \equiv -1$

Visa spoiler

I slutändan får man att $36! \equiv (18!)^2 (\mod 37) \equiv -1 (\mod 37)$ .

Det återstår att "dra kvadratroten ur -1 (mod 37)" för att bestämma 18! (mod 37). Man får dock två möjliga värden och man behöver klura ut vilket av de som är falsk lösning.

LuMa07 skrev:
Man kan utnyttja Wilsons sats i båda uppgifterna. (Jag har dock ingen aning om det är den optimala vägen till att lösa uppgifterna.)

2. Enligt Wilsons sats är $22! \equiv -1 (\mod 23)$ .

Det gäller att $22! = 20! \cdot 21 \cdot 22$ . Dessutom är $21 \equiv -2 (\mod 23)$ samt $22 \equiv -1 (\mod 23)$ .

Visa spoiler

Därmed är $20! \cdot (-2) \cdot (-1) \equiv -1 (\mod 23)$ och därmed $20! \cdot 2 \equiv 22 (\mod 23)$ .

1. Enligt Wilsons sats är $36! \equiv -1 (\mod 37)$ . Man kan utnyttja liknande knep här, nämligen

$19\equiv -18$ ,

$20 \equiv -17$

$21 \equiv -16$

...

$36 \equiv -1$

Visa spoiler

I slutändan får man att $36! \equiv (18!)^2 (\mod 37) \equiv -1 (\mod 37)$ .

Det återstår att "dra kvadratroten ur -1 (mod 37)" för att bestämma 18! (mod 37). Man får dock två möjliga värden och man behöver klura ut vilket av de som är falsk lösning.

Tack snälla för detta!! :)

Svara