Discrete Math for Computer Science, unit: Number Theory and Modular Arithmetic. Core concepts, terminology, and worked-example cues a college student meets for this unit, building on prior units without repeating them. Front: a term, concept, or short problem cue. Back: the definition, explanation, or answer.
16 cards · basic cards · AI-written, checked twice. Edit anything.
- What is number theory?
- The branch of mathematics studying integers and their properties
- What is a prime number?
- A natural number greater than 1 with no positive divisors other than 1 and itself
- What is a composite number?
- A natural number greater than 1 that has divisors other than 1 and itself
- What does it mean for one integer to divide another?
- The division results in a whole number with no remainder
- What is the greatest common divisor (GCD) of two integers?
- The largest positive integer that divides both numbers evenly
- What is the least common multiple (LCM) of two integers?
- The smallest positive integer that is a multiple of both numbers
- What is the Euclidean algorithm used for?
- Efficiently computing the greatest common divisor of two integers
- What is modular arithmetic?
- Arithmetic where numbers wrap around after reaching a fixed modulus value
- What does 'a is congruent to b modulo n' mean?
- a and b leave the same remainder when divided by n
- What is the modulo operation?
- An operation returning the remainder after division of one number by another
- What is the Fundamental Theorem of Arithmetic?
- Every integer greater than 1 has a unique prime factorization, up to order
- What is prime factorization?
- Expressing a number as a product of prime numbers
- What are two integers said to be if their GCD is 1?
- Relatively prime (or coprime)
- What is modular exponentiation used for?
- Efficiently computing large powers under a modulus, important in cryptography
- What is the significance of modular arithmetic in computer science?
- It underlies hashing, cryptography, and cyclic data structures like clocks and buffers
FlashKeepers