Ile rozwiązań ma kongruencja

[kasiczka15m]

Ile rozwiązań ma kongruencja \(\displaystyle{ x^{2}\equiv 991\pmod{151}}\)?
A kongruencja \(\displaystyle{ x^{18}\equiv 1\pmod{27}}\)?

[Vax]

1) \(\displaystyle{ x^2 \equiv 991 \equiv 991+3\cdot 151 \equiv 1444 \equiv 38^2 \pmod{151} \Leftrightarrow (x-38)(x+38) \equiv 0 \pmod{151}}\)

Czyli 2 rozwiązania.

2) Z tw. Eulera gdy \(\displaystyle{ (3,x) = 1}\) mamy \(\displaystyle{ x^{18} \equiv 1 \pmod{27}}\) wszystkich takich liczb, czyli rozwiązań jest 18.

[kasiczka15m]

A dlaczego bierzemy 991+3 *151?

Znam twierdzenie Eulera tylko w innych przypadkach gdy potega jest o jeden mniejsza od liczby modulo. Skad (3,x)=1?