**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Lecture# Number Theory: Primes

Description

This lecture covers the definition of primes and composites, the Fundamental Theorem of Arithmetic, proof by strong induction, trial division, the Sieve of Eratosthenes, and Euclid's Theorem on the infinitude of primes.

Login to watch the video

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

In course

Related concepts (49)

Related lectures (7)

CS-101: Advanced information, computation, communication I

Discrete mathematics is a discipline with applications to almost all areas of study. It provides a set of indispensable tools to computer science in particular. This course reviews (familiar) topics a

In algebra and number theory, Euclid's lemma is a lemma that captures a fundamental property of prime numbers, namely: For example, if p = 19, a = 133, b = 143, then ab = 133 × 143 = 19019, and since this is divisible by 19, the lemma implies that one or both of 133 or 143 must be as well. In fact, 133 = 19 × 7. If the premise of the lemma does not hold, i.e., p is a composite number, its consequent may be either true or false. For example, in the case of p = 10, a = 4, b = 15, composite number 10 divides ab = 4 × 15 = 60, but 10 divides neither 4 nor 15.

In mathematics, the sieve of Atkin is a modern algorithm for finding all prime numbers up to a specified integer. Compared with the ancient sieve of Eratosthenes, which marks off multiples of primes, the sieve of Atkin does some preliminary work and then marks off multiples of squares of primes, thus achieving a better theoretical asymptotic complexity. It was created in 2003 by A. O. L. Atkin and Daniel J. Bernstein. In the algorithm: All remainders are modulo-sixty remainders (divide the number by 60 and return the remainder).

In mathematics, the sieve of Sundaram is a variant of the sieve of Eratosthenes, a simple deterministic algorithm for finding all the prime numbers up to a specified integer. It was discovered by Indian student S. P. Sundaram in 1934. Start with a list of the integers from 1 to n. From this list, remove all numbers of the form i + j + 2ij where: The remaining numbers are doubled and incremented by one, giving a list of the odd prime numbers (i.e., all primes except 2) below 2n + 2.

In mathematics, the fundamental theorem of arithmetic, also called the unique factorization theorem and prime factorization theorem, states that every integer greater than 1 can be represented uniquely as a product of prime numbers, up to the order of the factors. For example, The theorem says two things about this example: first, that 1200 be represented as a product of primes, and second, that no matter how this is done, there will always be exactly four 2s, one 3, two 5s, and no other primes in the product.

A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways of writing it as a product, 1 × 5 or 5 × 1, involve 5 itself. However, 4 is composite because it is a product (2 × 2) in which both numbers are smaller than 4.

Explores elementary algebra concepts related to numeric sets and prime numbers, including unique factorization and properties.

Covers prime numbers, RSA cryptography, and primality testing, including the Chinese Remainder Theorem and the Miller-Rabin test.

Explores proof concepts, techniques, and applications in logic, mathematics, and algorithms.

Introduces logic, proofs, sets, functions, and algorithms in mathematics and computer science.

Explores RSA cryptography, covering primality testing, quadratic residues, and cryptographic applications.