Potęga modulo
Potęga modulo
Jakie \(\displaystyle{ x}\) spełniają \(\displaystyle{ (a^{31})^x \equiv a \pmod{271}}\) ?
-
Ponewor
- Moderator
- Posty: 2218
- Rejestracja: 30 sty 2012, o 21:05
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 70 razy
- Pomógł: 297 razy
Potęga modulo
Oczywiście. Treść zadania zinterpretowałem jako znajdź wszystkie takie \(\displaystyle{ x}\), dla których podana równość spełniona jest dla każdego \(\displaystyle{ a}\). Na wstępie zauważmy, że \(\displaystyle{ 271}\) jest liczbą pierwszą. Gdy \(\displaystyle{ 271 \mid a}\), to równość z treści zadania zachodzi trywialnie dla każdego \(\displaystyle{ x}\). Wobec tego możemy spokojnie założyć, że \(\displaystyle{ a}\) i \(\displaystyle{ 271}\) są względnie pierwsze i pomnożyć obie strony podanej równości przez element odwrotny do \(\displaystyle{ a}\), czyli \(\displaystyle{ a^{-1} \pmod{271}}\) po czym otrzymamy \(\displaystyle{ a^{31x-1} \equiv 1 \pmod{271}}\). Jak widać musi wobec tego zachodzić \(\displaystyle{ \mbox{ord}_{271}a \mid 31x-1}\). Istnieje takie \(\displaystyle{ a}\) (generator \(\displaystyle{ \mod 271}\)), dla którego \(\displaystyle{ \mbox{ord}_{271}a = 270}\). Wobec tego koniecznym jest by \(\displaystyle{ 270 \mid 31x-1}\). Jak widać na mocy Małego Twierdzenia Fermata jest to też warunkiem wystarczającym by podzielność zachodziła dla wszystkich \(\displaystyle{ a}\).
Zatem zadanie sprowadza się do rozwiązania podzielności \(\displaystyle{ 270 \mid 31x-1}\), czyli równania \(\displaystyle{ 31x-1=270y}\). Takie rzeczy się jakoś schematycznie robi z wykorzystaniem algorytmu Euklidesa, ale ja poradzę sobie bez niego. Patrząc na całe równanie \(\displaystyle{ \mod 3}\), widzimy, że \(\displaystyle{ x \equiv 1 \pmod{3}}\), czyli \(\displaystyle{ x=3x'+1}\). Po wstawieniu mamy \(\displaystyle{ 31\left( 3x'+1\right) -1=270y}\). Po redukcji mamy \(\displaystyle{ 31x'+10=90y}\). Patrząc na to ponownie \(\displaystyle{ \mod 3}\) mamy, że \(\displaystyle{ x'=3x''+2}\), a po wstawieniu i redukcji otrzymujemy \(\displaystyle{ 31x''+24=30y}\). Patrząc raz jeszcze \(\displaystyle{ \mod 3}\), mamy że \(\displaystyle{ x''=3x'''}\), co daje nam równanie \(\displaystyle{ 31x'''+8=10y}\). Jeżeli nie umiemy już odgadnąć wyniku, to patrzymy \(\displaystyle{ \mod 2}\) i widzimy, że \(\displaystyle{ x'''=2x''''}\), a co za tym idzie \(\displaystyle{ 31x''''+4=5y}\). Teraz już nie da się nie odgadnąć, że najmniejsze \(\displaystyle{ x''''}\) dające nam rozwiązanie, to \(\displaystyle{ x''''=1}\), a stąd \(\displaystyle{ x=61}\). A po prawdzie, to \(\displaystyle{ x \equiv 61 \pmod{270}}\).
Zatem zadanie sprowadza się do rozwiązania podzielności \(\displaystyle{ 270 \mid 31x-1}\), czyli równania \(\displaystyle{ 31x-1=270y}\). Takie rzeczy się jakoś schematycznie robi z wykorzystaniem algorytmu Euklidesa, ale ja poradzę sobie bez niego. Patrząc na całe równanie \(\displaystyle{ \mod 3}\), widzimy, że \(\displaystyle{ x \equiv 1 \pmod{3}}\), czyli \(\displaystyle{ x=3x'+1}\). Po wstawieniu mamy \(\displaystyle{ 31\left( 3x'+1\right) -1=270y}\). Po redukcji mamy \(\displaystyle{ 31x'+10=90y}\). Patrząc na to ponownie \(\displaystyle{ \mod 3}\) mamy, że \(\displaystyle{ x'=3x''+2}\), a po wstawieniu i redukcji otrzymujemy \(\displaystyle{ 31x''+24=30y}\). Patrząc raz jeszcze \(\displaystyle{ \mod 3}\), mamy że \(\displaystyle{ x''=3x'''}\), co daje nam równanie \(\displaystyle{ 31x'''+8=10y}\). Jeżeli nie umiemy już odgadnąć wyniku, to patrzymy \(\displaystyle{ \mod 2}\) i widzimy, że \(\displaystyle{ x'''=2x''''}\), a co za tym idzie \(\displaystyle{ 31x''''+4=5y}\). Teraz już nie da się nie odgadnąć, że najmniejsze \(\displaystyle{ x''''}\) dające nam rozwiązanie, to \(\displaystyle{ x''''=1}\), a stąd \(\displaystyle{ x=61}\). A po prawdzie, to \(\displaystyle{ x \equiv 61 \pmod{270}}\).