## hartnn 3 years ago Fermat's Little Theorem. a^{p-1}=(corresponds to)1mod p using this, we have remainder when 3^100 is divided by 101 as 1. Is this correct ? Can i have few more examples where this theorem is applied but not so directly... @mukushla

1. hartnn

@siddhantsharan , @sauravshakya

2. hartnn

yes, that was direct use of the theorem....

3. mukushla

i think we just use it directly

4. hartnn

any other interesting topic or theorem in modular arithmetic ?

5. mukushla

Wilson's theorem is interesting

6. hartnn

(n-1)!=-1(mod n) how do we use it ?

7. mukushla

If $$p$$ is a prime, then $$(p-1)!+1$$ is a multiple of $$p$$, that is$(p-1)! \equiv -1 \ \ \text{mod} \ p$

8. hartnn

i will be glad if someone posts a link for a good reference in this topic...

9. estudier

FLT is also a^p = a (mod p) Show that the two formulations are equivalent.

10. hartnn

divide by a on both sides? maybe.....

11. estudier

It's an iff type, so both ways......

12. hartnn

idk....maybe multiply both sides by a to get a^p = a (mod p) but is it correct to do so ?

13. estudier

On the right track, sort of...

14. estudier

a^p = a mod p, then if a not = 0 mod p then can cancel by a to get a^(p-1) = 1 mod p That's the first part...

15. hartnn

same for other part, right ?

16. estudier

Yes, more or less.....

17. estudier

FLT is also used in some combinatorial problems....

18. hartnn

u have some practice/examples with those ?

19. estudier

OK, you can try this one: Say you have enough beads in n colours, how many different necklaces consisting of p beads can be made, where p is prime?

20. hartnn

(mod(n/p))!

21. estudier

I guess I should tell you that you will need to think a bit in order to work it out, it is not straightforward....

22. estudier

Or I can tell you the answer and you can try to work it out.....

23. hartnn

let me try....after few minutes, u give answer...

24. estudier

I think u need more than a few minutes....:-)

25. hartnn

ok, whats the answer ?

26. estudier

(n^p-n)/2p + (n^((p+1)/2) -n)/2 + n

27. hartnn

OMG!

28. estudier

It's an integer so the first term still incorporates FLT...

29. estudier

Do you want links only about FLT/Wilsons or congruences/modular stuff as well....

30. hartnn

modular stuff as well...

31. estudier

Similar this http://www.math.sc.edu/~filaseta/gradcourses/Math780notes.pdf Or more detailed....

32. hartnn

thanks, i'll go through it......and will ask u for any doubts.