Use eulers theorem to find the least nonnegative residue modulo m of integer n

n=79^79, m=9

Printable View

- Oct 7th 2008, 08:51 PMrmpatel5eulers theorme
Use eulers theorem to find the least nonnegative residue modulo m of integer n

n=79^79, m=9 - Oct 7th 2008, 09:42 PMo_O
Note that: , i.e.

By Euler's theorem:

- Oct 7th 2008, 09:49 PMbigb
s

- Oct 7th 2008, 09:50 PMrmpatel5
- Oct 7th 2008, 10:00 PMo_O
Well we want to find: for some .

We have that

Not too hard to see how we get to .

As for calculating , you need to find its prime power decomposition. With this, use the fact that:

(1)

(2) is multiplicative which means

where is prime.

For example: