# Homework Help: Least positive integer, modular problem HELP!

1. Mar 25, 2012

### sg001

1. The problem statement, all variables and given/known data

find the least positive integer n for which 5$^{n}$ $\equiv$ 1 (mod17) or 5$^{n}$ $\equiv$ -1 (mod 17)

2. Relevant equations

3. The attempt at a solution

I really dont understand and method to doing these problems as I cant use a calculator and I can only work out powers maybe up to 4 or 5 (depending) in my head... the answer says its 8 but how would I work out in my head 5$^{8}$ +1 and then know it was divisible by 17???

2. Mar 26, 2012

### SteveL27

The trick is to keep reducing mod 17 as you go. So:

5^2 = 25 = 8 (mod 17)
5^4 = 8 * 8 = 64 = 13 = -4 (mod 17)
5^8 = (-4) * (-4) = 16 = -1 (mod 17)

If you wanted you could have computed 5^2, 5^3, 5^4, 5^5, ... the same way. But note that 5^16 = 1 (mod 17) by Fermat's little theorem. So if 5^n = 1 or 5^n = -1, n must divide 16. So we only have to check n = 2, 4, and 8.

3. Mar 26, 2012

### sg001

Thanks a bunch steve that cleared things up heaps!!!