# Urgent Help needed!

• Apr 9th 2006, 07:01 PM
jzon
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.
• Apr 9th 2006, 07:20 PM
ThePerfectHacker
Quote:

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.
• Apr 9th 2006, 10:24 PM
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
• Apr 10th 2006, 06:48 AM
ThePerfectHacker
Quote:

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)$