1. ## 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.

2. 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,
$\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.

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

THanks

4. 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 $\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)$