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.

Printable View

- Apr 9th 2006, 07:01 PMjzonUrgent 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 PMThePerfectHackerQuote:

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. - Apr 9th 2006, 10:24 PMjzon
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 AMThePerfectHackerQuote:

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