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
$\displaystyle \gcd(43,98)=1$ thus,
$\displaystyle 43^{\phi(98)}\equiv 1\mod 98$
Since, $\displaystyle \phi(98)=42$
Thus,
$\displaystyle 43^{42}\equiv 1\mod 98$
Squaring both sides,
$\displaystyle 43^{84}\equiv 1\mod 98$ (1)
--------
Notice that,
$\displaystyle 43^2\equiv 85\equiv -13$
Square,
$\displaystyle 43^4\equiv (-13)^2\equiv 71\equiv -27$ (2)
Square,
$\displaystyle 43^8\equiv (-27)^2 \equiv 43$ (3)
Mutiply (2) by (3),
$\displaystyle 43^{12}\equiv 15$ (4)
Now, multiply (1) by (4),
$\displaystyle 43^{96}\equiv 15$
Finally multiply both sides by 43,
$\displaystyle 43^{97}\equiv 15\cdot 43\equiv 57$
Thus,
$\displaystyle 43^{97}\equiv 57\mod 98$
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 $\displaystyle \gcd(a,n)=1$ and $\displaystyle \phi(n)$ is the number of integers relatively prime to $\displaystyle n$ but not exceeding, then,
$\displaystyle a^{\phi(n)}\equiv 1\mod n$"
Also, a formula for calculating the phi-function, with prime factoriztion.
If $\displaystyle n=p_1^{a_1}p_2^{a_2}...p_k^{a_k}$
Then, $\displaystyle \phi(n)=n\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)....\left(1-\frac{1}{p_k}\right)$