Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Lecture

Number Theory: Prime Numbers and Modular Arithmetic

Description

This lecture covers the concepts of prime numbers, modular arithmetic, and their applications. Topics include the properties of prime numbers, Wilson's theorem, complexity analysis, and practical examples of calculations involving prime numbers.

Official source

Ontological neighbourhood

Mathematics

Number theory: Topics in number theory

Related concepts (22)

Prime number

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.

Wilson's theorem

In algebra and number theory, Wilson's theorem states that a natural number n > 1 is a prime number if and only if the product of all the positive integers less than n is one less than a multiple of n. That is (using the notations of modular arithmetic), the factorial satisfies exactly when n is a prime number. In other words, any number n is a prime number if, and only if, (n − 1)! + 1 is divisible by n. This theorem was stated by Ibn al-Haytham (c. 1000 AD), and, in the 18th century, by the English mathematician John Wilson.

Modular arithmetic

In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" when reaching a certain value, called the modulus. The modern approach to modular arithmetic was developed by Carl Friedrich Gauss in his book Disquisitiones Arithmeticae, published in 1801. A familiar use of modular arithmetic is in the 12-hour clock, in which the day is divided into two 12-hour periods. If the time is 7:00 now, then 8 hours later it will be 3:00.

Number theory

Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and arithmetic functions. German mathematician Carl Friedrich Gauss (1777–1855) said, "Mathematics is the queen of the sciences—and number theory is the queen of mathematics." Number theorists study prime numbers as well as the properties of mathematical objects constructed from integers (for example, rational numbers), or defined as generalizations of the integers (for example, algebraic integers).

Euler's theorem

In number theory, Euler's theorem (also known as the Fermat–Euler theorem or Euler's totient theorem) states that, if n and a are coprime positive integers, and is Euler's totient function, then a raised to the power is congruent to 1 modulo n; that is In 1736, Leonhard Euler published a proof of Fermat's little theorem (stated by Fermat without proof), which is the restriction of Euler's theorem to the case where n is a prime number.

Related lectures (32)

Prime Numbers: Deterministic Approaches

Introduces deterministic approaches to identify prime numbers and covers algorithms and modular arithmetic for prime number testing.

Number Theory: Modular Exponentiation Examples

Covers examples of modular exponentiation, complexities, Lame's Theorem, Collatz Conjecture, and prime numbers.

Number Theory: Division, Remainder, Congruence

Covers number theory, division, remainder, congruence, prime numbers, integer representation, and the Euclidean algorithm.

Prime Numbers and Algorithms

Covers prime numbers, primality testing algorithms, modular arithmetic, and efficient exponentiation methods.

Fermat's Little Theorem