Math: Number Theory Basics

What is the divisibility rule for determining if a number is divisible by 3 or 9?

A number is divisible by 3 or 9 if the sum of its digits is divisible by 3 or 9, respectively.

How do you determine if a number is divisible by 11 using its digits?

A number is divisible by 11 if the alternating sum of its digits (adding and subtracting alternately) is divisible by 11 or is zero.

What is the Sieve of Eratosthenes used for in number theory?

The Sieve of Eratosthenes is an ancient algorithm used to find all prime numbers up to a specified integer by iteratively marking the multiples of each prime.

What does the Fundamental Theorem of Arithmetic state about integers greater than 1?

The Fundamental Theorem of Arithmetic states that every integer greater than 1 is either a prime itself or can be uniquely factored into a product of primes, up to the order of the factors.

What is the formula connecting the Greatest Common Divisor (GCD) and Least Common Multiple (LCM) of two positive integers a and b?

The product of the GCD and LCM of two positive integers equals the product of the numbers themselves: GCD(a, b) * LCM(a, b) = a * b.

What does it mean for two integers a and b to be congruent modulo n (a ≡ b mod n)?

Two integers a and b are congruent modulo n if their difference (a - b) is an integer multiple of n, meaning they leave the same remainder when divided by n.

What are the divisibility rules for determining if a number is divisible by 4 and 8?

A number is divisible by 4 if its last two digits form a number divisible by 4, and it is divisible by 8 if its last three digits form a number divisible by 8.

What is the divisibility rule for 6?

A number is divisible by 6 if it satisfies the divisibility rules for both 2 (it is an even number) and 3 (the sum of its digits is divisible by 3).

How does the Euclidean algorithm find the Greatest Common Divisor (GCD) of two numbers a and b?

The Euclidean algorithm repeatedly replaces the larger number with the remainder of dividing the larger by the smaller, until the remainder is zero; the last non-zero remainder is the GCD.

What is the formula for Fermat's Little Theorem, assuming p is a prime and a is an integer not divisible by p?

Fermat's Little Theorem states that a^(p-1) ≡ 1 (mod p). Alternatively, for any integer a, a^p ≡ a (mod p).