Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

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

  • This Question is Closed
  1. hartnn
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 3

    @siddhantsharan , @sauravshakya

  2. hartnn
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 3

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

  3. mukushla
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    i think we just use it directly

  4. hartnn
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 3

    any other interesting topic or theorem in modular arithmetic ?

  5. mukushla
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Wilson's theorem is interesting

  6. hartnn
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 3

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

  7. mukushla
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 3

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

  9. estudier
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  10. hartnn
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 3

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

  11. estudier
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  12. hartnn
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 3

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

  13. estudier
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    On the right track, sort of...

  14. estudier
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    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
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 3

    same for other part, right ?

  16. estudier
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    Yes, more or less.....

  17. estudier
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  18. hartnn
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 3

    u have some practice/examples with those ?

  19. estudier
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    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
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 3

    (mod(n/p))!

  21. estudier
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    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
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  23. hartnn
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 3

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

  24. estudier
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  25. hartnn
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 3

    ok, whats the answer ?

  26. estudier
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  27. hartnn
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 3

    OMG!

  28. estudier
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  29. estudier
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  30. hartnn
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 3

    modular stuff as well...

  31. estudier
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  32. hartnn
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 3

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

  33. Not the answer you are looking for?
    Search for more explanations.

    • Attachments:

Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy