Division theorem, Euclidean algorithm and Bezout's identity 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 the division theorem.
- For , with unique integers and .
- What is the key fact behind the Euclidean algorithm?
- where .
- How does the Euclidean algorithm give the hcf?
- Repeat on divisor and remainder; the last non-zero remainder is the hcf.
- What does coprime mean?
- The hcf of the two integers is .
- Formula for the lcm using the hcf?
- .
- State Bezout's identity.
- There are integers with .
- How do you find and in Bezout's identity?
- Back substitution: write each remainder as and work upwards from the hcf.
- hcf and lcm of and ?
- hcf , lcm .
- Bezout combination for and ?
- .
- When does have integer solutions?
- If and only if divides .
- Why has no integer solutions?
- The hcf is , so the left side is always a multiple of , and .
- Write as .
- .