Thread: Urgent Help needed!

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.

Originally Posted by jzon

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,
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.

Is this the same as Fermat's Little Theorem??? I would appreciate if some1 could give the solution using fermat's little theorem

THanks

Originally Posted by jzon

Is this the same as Fermat's Little Theorem??? I would appreciate if some1 could give the solution using fermat's little theorem

THanks

Almost.
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,