## hartnn Group Title 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 one year ago one year ago

1. hartnn Group Title

@siddhantsharan , @sauravshakya

2. hartnn Group Title

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

3. mukushla Group Title

i think we just use it directly

4. hartnn Group Title

any other interesting topic or theorem in modular arithmetic ?

5. mukushla Group Title

Wilson's theorem is interesting

6. hartnn Group Title

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

7. mukushla Group Title

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 Group Title

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

9. estudier Group Title

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

10. hartnn Group Title

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

11. estudier Group Title

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

12. hartnn Group Title

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

13. estudier Group Title

On the right track, sort of...

14. estudier Group Title

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 Group Title

same for other part, right ?

16. estudier Group Title

Yes, more or less.....

17. estudier Group Title

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

18. hartnn Group Title

u have some practice/examples with those ?

19. estudier Group Title

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 Group Title

(mod(n/p))!

21. estudier Group Title

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 Group Title

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

23. hartnn Group Title

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

24. estudier Group Title

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

25. hartnn Group Title

26. estudier Group Title

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

27. hartnn Group Title

OMG!

28. estudier Group Title

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

29. estudier Group Title

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

30. hartnn Group Title

modular stuff as well...

31. estudier Group Title

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

32. hartnn Group Title

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