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.
38 cards · basic cards · AI-written, checked twice. Edit anything.
- What is number theory?
Show answer
The branch of mathematics studying integers and their properties- What is a prime number?
Show answer
A natural number greater than 1 with no positive divisors other than 1 and itself- What is a composite number?
Show answer
A natural number greater than 1 that has divisors other than 1 and itself- What does it mean for one integer to divide another?
Show answer
The division results in a whole number with no remainder- What is the greatest common divisor (GCD) of two integers?
Show answer
The largest positive integer that divides both numbers evenly- What is the least common multiple (LCM) of two integers?
Show answer
The smallest positive integer that is a multiple of both numbers- What is the Euclidean algorithm used for?
Show answer
Efficiently computing the greatest common divisor of two integers- What is modular arithmetic?
Show answer
Arithmetic where numbers wrap around after reaching a fixed modulus value- What does 'a is congruent to b modulo n' mean?
Show answer
a and b leave the same remainder when divided by n- What is the modulo operation?
Show answer
An operation returning the remainder after division of one number by another- What is the Fundamental Theorem of Arithmetic?
Show answer
Every integer greater than 1 has a unique prime factorization, up to order- What is prime factorization?
Show answer
Expressing a number as a product of prime numbers- What are two integers said to be if their GCD is 1?
Show answer
Relatively prime (or coprime)- What is modular exponentiation used for?
Show answer
Efficiently computing large powers under a modulus, important in cryptography- What is the significance of modular arithmetic in computer science?
Show answer
It underlies hashing, cryptography, and cyclic data structures like clocks and buffers
FlashKeepers