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, 08: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, 08:20 PMThePerfectHackerQuote:

Originally Posted by**jzon**

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. - Apr 9th 2006, 11: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, 07:48 AMThePerfectHackerQuote:

Originally Posted by**jzon**

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,