Session 4B
Primes and gcd basics
45-75 min - work through lesson notes, practice, and the MCQ check.
In progress
Account sync
Sign in to keep this session synced across devices.
Account sync disabled
Add Supabase environment variables to enable account sync. Progress is saved locally in this browser for now.
Session tips
- Finish the MCQ before marking complete.
- Check the answer outlines after trying on paper.
- Mark complete to update your certificate progress.
Lesson notes
- A prime is a positive integer p > 1 whose only positive divisors are 1 and p. Prime numbers are central because they behave like "atomic" divisibility objects. A major tool is Euclid's Lemma: if p is prime and p | ab, then p | a or p | b. This is not true for non-primes. For example, 6 | (2*3) but 6 does not divide 2 or 3. Euclid's Lemma is what makes prime factorization and many number theory arguments work.
- At a beginner level, you can treat Euclid's Lemma as a theorem you are allowed to use, but it's still important to know how it is used: it lets you pull a prime divisor out of a product. For instance, if p | a^2, then p | a because a^2 = a*a and the lemma says p divides one of the a's, which is the same as p | a. As you get further, you'll connect this to gcd arguments and Bezout's identity, but early on the main goal is learning how primes interact with products in proofs.
Practice
- 1Prove: If p is prime and p | a^2 then p | a.
- 2Prove: If gcd(a,b) = 1 and a | bc then a | c.
Show answers / outlines
Answers
- 1Apply Euclid's Lemma to p | a*a.
- 2Use Bezout or modular reasoning.
MCQ
Euclid's Lemma says: if p is prime and p | ab, then: