Fermat's little theorem and congruence equations Flashcards
Studying this course? Keep your progress in one place.

Flip each card. Be honest: the ones you mark Not yet come back first.
12 cards
Tap a card to flip it. Swipe right if you knew it, left if not.
See all 12 cards
- State Fermat's little theorem.
- If is prime and , then .
- Alternative form of Fermat's little theorem?
- for any integer .
- How do you reduce ?
- Write ; then .
- Least positive residue of modulo ?
- .
- Remainder when is divided by ?
- , .
- When does have a solution?
- If and only if divides .
- How many solutions modulo does it have?
- Exactly solutions (when ).
- What is the multiplicative inverse of modulo ?
- A number with ; it exists iff .
- How do you find a multiplicative inverse?
- Euclidean algorithm, then Bezout back substitution: gives .
- Inverse of modulo ?
- (or ), since .
- Solve .
- Inverse of 7 is 8, so .
- Solve a congruence when and .
- Divide through by (including the modulus), solve, then list solutions modulo .