Eναλλακτικός (και πιο εποπτικός) τρόπος: 111=3*37 ,3 και 37 σχετικά πρώτοι. Οπότε οι λύσεις mod(3) και mod(37)θα δίνουν μέσω συστήματος- κατά μοναδικό τρόπο- λύση mod(111). (To Θεώρημα του κινέζικου υπολοίπου-Chinese remainder theorem) a^37≡a mod(37)[μικρό Θ.Φερμά] 102^73=102^(2*36)*102≡18 μοδ(37) (=102) άρα η αρχική = 18+55=9mod(37) a^37=a mod(3) (Φερμά),102^73 ≡ 0 mod(3) και 55 ≡ 1 mod 3 έτσι το σύστημα: a ≡ 1 mod 3 (1) a ≡ 9 mod 37 (2) ...μοναδική λύση mod(111)=46
Mε χρήση Φερμά-Όϋλερ
ΑπάντησηΔιαγραφή(102^73 +55)^37 mod(111)=(102^73 +55)mod(111)
=102^73 mod111 +55mod(111)=102 +55 =157mod(111)=46
Eναλλακτικός (και πιο εποπτικός) τρόπος:
ΑπάντησηΔιαγραφή111=3*37 ,3 και 37 σχετικά πρώτοι. Οπότε οι λύσεις mod(3) και mod(37)θα δίνουν μέσω συστήματος- κατά μοναδικό τρόπο- λύση mod(111). (To Θεώρημα του κινέζικου υπολοίπου-Chinese remainder theorem)
a^37≡a mod(37)[μικρό Θ.Φερμά]
102^73=102^(2*36)*102≡18 μοδ(37) (=102)
άρα η αρχική = 18+55=9mod(37)
a^37=a mod(3) (Φερμά),102^73 ≡ 0 mod(3)
και 55 ≡ 1 mod 3
έτσι το σύστημα:
a ≡ 1 mod 3 (1)
a ≡ 9 mod 37 (2)
...μοναδική λύση mod(111)=46