Least positive integer, modular problem HELP

[sg001]

Homework Statement

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

Homework Equations

The Attempt at a Solution

I really don't understand and method to doing these problems as I can't 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?

There must be an easier way,,, please help!

 

[SteveL27]

Homework Statement

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

Homework Equations

The Attempt at a Solution

I really don't understand and method to doing these problems as I can't 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?

There must be an easier way,,, please help!

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.

 

[sg001]

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.

Thanks a bunch steve that cleared things up heaps!