Matematyka.pl

Korzystając z tw. Eulera obliczyć \(\displaystyle{ r_{35} (14^{320})}\).

Jak tutaj zastosować tw. Eulera skoro 35 i 14 nie są względnie pierwsze?

Jak tutaj zastosować tw. Eulera

Nie stosować Wskazówka: \(\displaystyle{ 14^2=-14 \mod35}\).

Pozdrawiam.

A możesz mi powiedzieć jak na to wpadłaś? Czy poprawny wynik to \(\displaystyle{ 14}\)?

A w takim przykladzie: \(\displaystyle{ r_{28}(35^{320})}\) możemy zauważyć, że \(\displaystyle{ 35 = 7 \mod 28}\) oraz \(\displaystyle{ 7^2 = -7 \mod 28}\) ?

I ostatni przykład: \(\displaystyle{ r_{45}(28^{320})}\). Tutaj ta sztuczka już chyba nie działa, ale mogę skorzystać, z tw. Eulera. Dostaję z niego, że
\(\displaystyle{ r_{45}(28^{320}) = r_{45}(28^{12}) = r_{45}(17^{12}) = r_{45}((17^{2})^6) = r_{45}(19^{6}) = r_{45}((19^{2})^3) = r_{45}(1^{3}) = 1}\)

Bedę wdzieczny za sprawdzenie.

MichTrz pisze:A możesz mi powiedzieć jak na to wpadłaś?

Nie wpadałam. Po prostu obliczyłam: \(\displaystyle{ 14^2=196=21=-14\mod 35}\). Skoro nie można skorzystać wprost z tw. Eulera, to trzeba obliczyć inaczej.

MichTrz pisze:Czy poprawny wynik to \(\displaystyle{ 14}\)?

Nie. Liczmy dalej: \(\displaystyle{ 14^3=14^2\cdot 14=-14\cdot 14=14\mod 35}\) i już widać wzór: dla nieparzystych potęg \(\displaystyle{ n}\) masz \(\displaystyle{ 14^n=14\mod 35}\), a dla parzystych \(\displaystyle{ 14^n=-14\mod 35}\), zatem \(\displaystyle{ 14^{320}=-14=21\mod 35}\).

MichTrz pisze:A w takim przykladzie: \(\displaystyle{ r_{28}(35^{320})}\) możemy zauważyć, że \(\displaystyle{ 35 = 7 \mod 28}\) oraz \(\displaystyle{ 7^2 = -7 \mod 28}\) ?

Ano.

MichTrz pisze:\(\displaystyle{ r_{45}(28^{320}) = r_{45}(28^{12})}\)

A skąd to się wzięło?

Pozdrawiam.