3.2 Prime numbers

Achievable AMC

3. Number theory

Prime numbers

4 min read

Font

Discuss

Feedback

This chapter applies to all AMC 8/10/12 test takers.

Prime numbers show up constantly on the AMC. A prime number is a positive integer that has exactly two positive divisors: $1$ and itself. The only even prime is $2$ .

You’ll want to recognize any prime number below $100$ , and you should be able to list all primes below $50$ from memory. Try writing them out, then compare your list to the one below.

(spoiler)

$2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47$

Why are prime numbers important?

In the real world, primes matter in cryptography, computer science, and even music. On the AMC, primes appear in many settings, especially problems involving:

prime factorization
GCD and LCM
modular arithmetic
relatively prime integers

Prime factorization

A common way to find a prime factorization is the factor tree method. The idea is simple:

Split the number into two factors.
Keep factoring any composite factors.
Stop when every branch ends in a prime.

The prime factorization is the list of primes at the ends of the branches (including repeats). You don’t need to worry about picking “the right” factors at each step: no matter which factors you choose first, you’ll end with the same prime factorization.

$60 / \ 415 / \ / \ 2235$

As shown above, the prime factorization of $60$ is $2^{2} \times 3^{1} \times 5^{1}$ .

Example: The question below is from 2007 AMC 8

What is the sum of the two smallest prime factors of $250$ ?
A. $2$
B. $5$
C. $7$
D. $10$
E. $12$

(spoiler)

Answer: C. $7$

Modular arithmetic and primes

Fermat’s Little Theorem is a useful tool in modular arithmetic. It says

If $p$ is prime and $a$ is not divisible by $p$ , then raising $a$ to the power $p - 1$ leaves a remainder of $1$ when divided by $p$ .

$a^{p - 1} \equiv 1 (mod p)$

For example, take $a = 8$ and $p = 3$ . Since $3$ does not divide $8$ , Fermat’s Little Theorem applies, so $8^{3 - 1} \equiv 1$ (mod $3$ ).

$a = 8$ , $p = 3$

$\frac{a ^{p - 1}}{p}$ = $\frac{8 ^{3 - 1}}{3}$

$\frac{8 ^{2}}{3}$ = $\frac{64}{3}$

$21$ remainder $1$

Example: The question below is from 2017 AMC 10B

An integer $N$ is selected at random in the range $1 \leq N \leq 2020$ . What is the probability that the remainder when $N^{16}$ is divided by $5$ is $1$ ?
A. $\frac{1}{5}$
B. $\frac{2}{5}$
C. $\frac{3}{5}$
D. $\frac{4}{5}$
E. $1$

(spoiler)

Answer: D. $\frac{4}{5}$

Relatively prime integers

Two integers are relatively prime (or coprime) if they share no common prime factors. The numbers themselves do not have to be prime.

For example, $14$ and $25$ are relatively prime. Even though neither number is prime, they have no common divisor other than $1$ .

Example: The question below is from 2021 AMC 12A

Consider the set of all fractions $\frac{x}{y}$ , where $x$ and $y$ are relatively prime positive integers. How many of these fractions have the property that if both numerator and denominator are increased by $1$ , the value of the fraction is increased by $10%$ ?
A. $0$
B. $1$
C. $2$
D. $3$
E. $infinitely many$

(spoiler)

Answer: B. $1$

Common themes

A semiprime is any number that is the product of two prime numbers.
Don’t expect to factor with extremely large primes.
Look out for Mersenne primes: $2^{n} - 1$ . The most relevant Mersenne primes are $3, 7, 31, 127$ .

Prime numbers basics

Prime: positive integer with exactly two positive divisors (1 and itself)
Only even prime: 2
Know all primes below 50; recognize primes below 100Importance of primes on AMC
Appear in problems involving:
- Prime factorization
- GCD and LCM
- Modular arithmetic
- Relatively prime integersPrime factorization
Use factor tree: split into factors until all are prime
Prime factorization is unique (up to order)
Example: $60 = 2^{2} \times 3^{1} \times 5^{1}$ Modular arithmetic and primes
Fermat’s Little Theorem: $a^{p - 1} \equiv 1 (mod p)$ if $p$ is prime and $p ∤ a$
Useful for finding remainders in exponentiation problemsRelatively prime integers
Two numbers are relatively prime if they share no common prime factors
Numbers do not need to be prime themselvesCommon themes
Semiprime: product of two primes
Mersenne primes: numbers of form $2^{n} - 1$ (notable examples: 3, 7, 31, 127)
AMC problems rarely require factoring very large primes

Next | 3.3 Modular arithmetic

Prime numbers

This chapter applies to all AMC 8/10/12 test takers.

Prime numbers show up constantly on the AMC. A prime number is a positive integer that has exactly two positive divisors: $1$ and itself. The only even prime is $2$ .

You’ll want to recognize any prime number below $100$ , and you should be able to list all primes below $50$ from memory. Try writing them out, then compare your list to the one below.

(spoiler)

$2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47$

Why are prime numbers important?

In the real world, primes matter in cryptography, computer science, and even music. On the AMC, primes appear in many settings, especially problems involving:

prime factorization
GCD and LCM
modular arithmetic
relatively prime integers

Prime factorization

A common way to find a prime factorization is the factor tree method. The idea is simple:

Split the number into two factors.
Keep factoring any composite factors.
Stop when every branch ends in a prime.

$60 / \ 415 / \ / \ 2235$

As shown above, the prime factorization of $60$ is $2^{2} \times 3^{1} \times 5^{1}$ .

Example: The question below is from 2007 AMC 8

What is the sum of the two smallest prime factors of $250$ ?
A. $2$
B. $5$
C. $7$
D. $10$
E. $12$

(spoiler)

Answer: C. $7$

Modular arithmetic and primes

Fermat’s Little Theorem is a useful tool in modular arithmetic. It says

If $p$ is prime and $a$ is not divisible by $p$ , then raising $a$ to the power $p - 1$ leaves a remainder of $1$ when divided by $p$ .

$a^{p - 1} \equiv 1 (mod p)$

For example, take $a = 8$ and $p = 3$ . Since $3$ does not divide $8$ , Fermat’s Little Theorem applies, so $8^{3 - 1} \equiv 1$ (mod $3$ ).

$a = 8$ , $p = 3$

$\frac{a ^{p - 1}}{p}$ = $\frac{8 ^{3 - 1}}{3}$

$\frac{8 ^{2}}{3}$ = $\frac{64}{3}$

$21$ remainder $1$

Example: The question below is from 2017 AMC 10B

An integer $N$ is selected at random in the range $1 \leq N \leq 2020$ . What is the probability that the remainder when $N^{16}$ is divided by $5$ is $1$ ?
A. $\frac{1}{5}$
B. $\frac{2}{5}$
C. $\frac{3}{5}$
D. $\frac{4}{5}$
E. $1$

(spoiler)

Answer: D. $\frac{4}{5}$

Relatively prime integers

Two integers are relatively prime (or coprime) if they share no common prime factors. The numbers themselves do not have to be prime.

For example, $14$ and $25$ are relatively prime. Even though neither number is prime, they have no common divisor other than $1$ .

Example: The question below is from 2021 AMC 12A

Consider the set of all fractions $\frac{x}{y}$ , where $x$ and $y$ are relatively prime positive integers. How many of these fractions have the property that if both numerator and denominator are increased by $1$ , the value of the fraction is increased by $10%$ ?
A. $0$
B. $1$
C. $2$
D. $3$
E. $infinitely many$

(spoiler)

Answer: B. $1$

Common themes

A semiprime is any number that is the product of two prime numbers.
Don’t expect to factor with extremely large primes.
Look out for Mersenne primes: $2^{n} - 1$ . The most relevant Mersenne primes are $3, 7, 31, 127$ .

Achievable AMC

3. Number theory

Prime numbers

4 min read

Font

Discuss

Feedback

This chapter applies to all AMC 8/10/12 test takers.

Prime numbers show up constantly on the AMC. A prime number is a positive integer that has exactly two positive divisors: $1$ and itself. The only even prime is $2$ .

You’ll want to recognize any prime number below $100$ , and you should be able to list all primes below $50$ from memory. Try writing them out, then compare your list to the one below.

(spoiler)

$2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47$

Why are prime numbers important?

In the real world, primes matter in cryptography, computer science, and even music. On the AMC, primes appear in many settings, especially problems involving:

prime factorization
GCD and LCM
modular arithmetic
relatively prime integers

Prime factorization

A common way to find a prime factorization is the factor tree method. The idea is simple:

Split the number into two factors.
Keep factoring any composite factors.
Stop when every branch ends in a prime.

$60 / \ 415 / \ / \ 2235$

As shown above, the prime factorization of $60$ is $2^{2} \times 3^{1} \times 5^{1}$ .

Example: The question below is from 2007 AMC 8

What is the sum of the two smallest prime factors of $250$ ?
A. $2$
B. $5$
C. $7$
D. $10$
E. $12$

(spoiler)

Answer: C. $7$

Modular arithmetic and primes

Fermat’s Little Theorem is a useful tool in modular arithmetic. It says

If $p$ is prime and $a$ is not divisible by $p$ , then raising $a$ to the power $p - 1$ leaves a remainder of $1$ when divided by $p$ .

$a^{p - 1} \equiv 1 (mod p)$

For example, take $a = 8$ and $p = 3$ . Since $3$ does not divide $8$ , Fermat’s Little Theorem applies, so $8^{3 - 1} \equiv 1$ (mod $3$ ).

$a = 8$ , $p = 3$

$\frac{a ^{p - 1}}{p}$ = $\frac{8 ^{3 - 1}}{3}$

$\frac{8 ^{2}}{3}$ = $\frac{64}{3}$

$21$ remainder $1$

Example: The question below is from 2017 AMC 10B

An integer $N$ is selected at random in the range $1 \leq N \leq 2020$ . What is the probability that the remainder when $N^{16}$ is divided by $5$ is $1$ ?
A. $\frac{1}{5}$
B. $\frac{2}{5}$
C. $\frac{3}{5}$
D. $\frac{4}{5}$
E. $1$

(spoiler)

Answer: D. $\frac{4}{5}$

Relatively prime integers

Two integers are relatively prime (or coprime) if they share no common prime factors. The numbers themselves do not have to be prime.

For example, $14$ and $25$ are relatively prime. Even though neither number is prime, they have no common divisor other than $1$ .

Example: The question below is from 2021 AMC 12A

Consider the set of all fractions $\frac{x}{y}$ , where $x$ and $y$ are relatively prime positive integers. How many of these fractions have the property that if both numerator and denominator are increased by $1$ , the value of the fraction is increased by $10%$ ?
A. $0$
B. $1$
C. $2$
D. $3$
E. $infinitely many$

(spoiler)

Answer: B. $1$

Common themes

A semiprime is any number that is the product of two prime numbers.
Don’t expect to factor with extremely large primes.
Look out for Mersenne primes: $2^{n} - 1$ . The most relevant Mersenne primes are $3, 7, 31, 127$ .

Prime numbers basics

Prime: positive integer with exactly two positive divisors (1 and itself)
Only even prime: 2
Know all primes below 50; recognize primes below 100Importance of primes on AMC
Appear in problems involving:
- Prime factorization
- GCD and LCM
- Modular arithmetic
- Relatively prime integersPrime factorization
Use factor tree: split into factors until all are prime
Prime factorization is unique (up to order)
Example: $60 = 2^{2} \times 3^{1} \times 5^{1}$ Modular arithmetic and primes
Fermat’s Little Theorem: $a^{p - 1} \equiv 1 (mod p)$ if $p$ is prime and $p ∤ a$
Useful for finding remainders in exponentiation problemsRelatively prime integers
Two numbers are relatively prime if they share no common prime factors
Numbers do not need to be prime themselvesCommon themes
Semiprime: product of two primes
Mersenne primes: numbers of form $2^{n} - 1$ (notable examples: 3, 7, 31, 127)
AMC problems rarely require factoring very large primes

Next | 3.3 Modular arithmetic

Prime numbers

This chapter applies to all AMC 8/10/12 test takers.

Prime numbers show up constantly on the AMC. A prime number is a positive integer that has exactly two positive divisors: $1$ and itself. The only even prime is $2$ .

You’ll want to recognize any prime number below $100$ , and you should be able to list all primes below $50$ from memory. Try writing them out, then compare your list to the one below.

(spoiler)

$2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47$

Why are prime numbers important?

In the real world, primes matter in cryptography, computer science, and even music. On the AMC, primes appear in many settings, especially problems involving:

prime factorization
GCD and LCM
modular arithmetic
relatively prime integers

Prime factorization

A common way to find a prime factorization is the factor tree method. The idea is simple:

Split the number into two factors.
Keep factoring any composite factors.
Stop when every branch ends in a prime.

$60 / \ 415 / \ / \ 2235$

As shown above, the prime factorization of $60$ is $2^{2} \times 3^{1} \times 5^{1}$ .

Example: The question below is from 2007 AMC 8

What is the sum of the two smallest prime factors of $250$ ?
A. $2$
B. $5$
C. $7$
D. $10$
E. $12$

(spoiler)

Answer: C. $7$

Modular arithmetic and primes

Fermat’s Little Theorem is a useful tool in modular arithmetic. It says

If $p$ is prime and $a$ is not divisible by $p$ , then raising $a$ to the power $p - 1$ leaves a remainder of $1$ when divided by $p$ .

$a^{p - 1} \equiv 1 (mod p)$

For example, take $a = 8$ and $p = 3$ . Since $3$ does not divide $8$ , Fermat’s Little Theorem applies, so $8^{3 - 1} \equiv 1$ (mod $3$ ).

$a = 8$ , $p = 3$

$\frac{a ^{p - 1}}{p}$ = $\frac{8 ^{3 - 1}}{3}$

$\frac{8 ^{2}}{3}$ = $\frac{64}{3}$

$21$ remainder $1$

Example: The question below is from 2017 AMC 10B

An integer $N$ is selected at random in the range $1 \leq N \leq 2020$ . What is the probability that the remainder when $N^{16}$ is divided by $5$ is $1$ ?
A. $\frac{1}{5}$
B. $\frac{2}{5}$
C. $\frac{3}{5}$
D. $\frac{4}{5}$
E. $1$

(spoiler)

Answer: D. $\frac{4}{5}$

Relatively prime integers

Two integers are relatively prime (or coprime) if they share no common prime factors. The numbers themselves do not have to be prime.

For example, $14$ and $25$ are relatively prime. Even though neither number is prime, they have no common divisor other than $1$ .

Example: The question below is from 2021 AMC 12A

Consider the set of all fractions $\frac{x}{y}$ , where $x$ and $y$ are relatively prime positive integers. How many of these fractions have the property that if both numerator and denominator are increased by $1$ , the value of the fraction is increased by $10%$ ?
A. $0$
B. $1$
C. $2$
D. $3$
E. $infinitely many$

(spoiler)

Answer: B. $1$

Common themes

A semiprime is any number that is the product of two prime numbers.
Don’t expect to factor with extremely large primes.
Look out for Mersenne primes: $2^{n} - 1$ . The most relevant Mersenne primes are $3, 7, 31, 127$ .