Using the fact that reduction can be carried out at each stage without changing the end result, calculate 43^97(mod 98) exactly using only the capabilites of a standard pocket calculator.
You can use a theorem called "Euler's Generalization of Fermat's Theorem" which means, that since,Originally Posted by jzon
thus,
Since,
Thus,
Squaring both sides,
(1)
--------
Notice that,
Square,
(2)
Square,
(3)
Mutiply (2) by (3),
(4)
Now, multiply (1) by (4),
Finally multiply both sides by 43,
Thus,
Without Euler's Theorem this can still be done but only much longer.
Almost.Originally Posted by jzon
You cannot use Fermat's Little Theorem because 98 is not prime.
But you can use another:
"If and is the number of integers relatively prime to but not exceeding, then,
"
Also, a formula for calculating the phi-function, with prime factoriztion.
If
Then,