19^92 is (19^4)^23, and we can do the raising to the power by repeated multiplication mod 92.
19^4 = 130,321, which is 49 mod 92. This has to be raised to the 23rd power. Repeated multiplication by 49 and taking mod 92 gives:
49
* 49 = 2401 = 9 mod 92 (square)
* 49 = 441 = 73 mod 92 (cube)
* 49 = 3577 = 81 mod 92 (4th power)
* 49 = 3969 = 13 mod 92 (5th power)
* 49 = 637 = 85 mod 92 (6th power)
* 49 = 4165 = 25 mod 92 (7th power)
* 49 = 1225 = 29 mod 92 (8th power)
* 49 = 1421 = 41 mod 92 (9th power)
* 49 = 2009 = 77 mod 92 (10th power)
* 49 = 3773 = 1 mod 92 (11th power)
which means this can be stopped here: 49^11 = 1 mod 92, so 49^22 mod 92 = 1, and then 49^23 mod 92 = 49.
|
Posted by Charlie
on 2006-05-02 09:25:35 |