Concept 25.0.1 · Algebraic Number Theory Techniques
- Make substitutions to convert numbers to variables
- Group terms
- Look for factorizations
- Sometimes use modular arithmetic, divisibility, or other number theory techniques
Turn numbers into variables, then factor: difference of squares, sums and differences of cubes, Simon's trick and Sophie Germain crack contest number theory.
In this section you will be able to turn numbers into variables, then factor with the difference of squares.
a divides b and c, and a + b + c = 100. Substitute b = ax and c = ay, and the sum factors: a(1 + x + y) = 100.
Number theory problems often hide algebra. Give the messy part a name, like or , and look for a factorization.
The star tool is the difference of squares, . It’s Theorem 12.2.1 from Chapter 12, now aimed at whole numbers: one big number becomes a product of two smaller ones.
These are the same rules as Theorem 12.0.1 in Chapter 12.
Same identity as Theorem 12.2.1. In number theory, it turns one big number into a product of two smaller ones.
: the middle terms cancel.
Find the number of ordered triples where , , and are positive integers, is a factor of , is a factor of , and .
divides and . Substitute and with positive integers . What does become?
How many values of from to inclusive make a multiple of ?
Substitute . Then . What does the expression become?
There is a positive integer such that . What is the sum of the digits of ?
The ages of Jonie's four cousins are distinct single-digit positive integers. Two of the cousins' ages multiplied together give , while the other two multiply to . What is the sum of the ages of Jonie's four cousins?
How many ordered pairs of positive integers, with , have the property that their squares differ by ?
Which of the following is equivalent to
There exists a unique strictly increasing sequence of nonnegative integers such that
What is ?
In this section you will be able to factor sums and differences of cubes and use them to find remainders.
Is n³ + 1 ever prime? Factor it as (n + 1)(n² − n + 1) and you’ll see: almost never.
Cubes factor too (Theorems 12.3.1 and 12.3.2 from Chapter 12). The second factor is a quadratic: for a difference, for a sum.
A related fact: . When you work mod , you can replace by inside any polynomial.
Same identity as Theorem 12.3.1.
.
Same identity as Theorem 12.3.2.
Replace by in the difference of cubes: .
Find the sum of all positive integers such that when is divided by , the remainder is .
The sum of the first cubes has a closed form. Which one?
What is the greatest three-digit positive integer for which the sum of the first positive integers is not a divisor of the product of the first positive integers?
For each integer , let be the sum of all products , where and are integers and . What is the sum of the least values of such that is divisible by ?
In this section you will be able to use Simon's Favorite Factoring Trick to turn xy, x and y terms into a product.
ab − 4a − 4b + 8 = 0 looks stuck. Add 8 to both sides and it becomes (a − 4)(b − 4) = 8.
Simon’s trick (Theorem 12.4.2 in Chapter 12) adds the right constant so that factors as , minus .
Once you have a product equal to a number, list its factor pairs, negatives included, and keep the ones that fit the problem.
Same trick as Theorem 12.4.2.
Expand: .
You can generally apply this factorization when you have , , and terms. After applying the factorization, you can then find all possible values for each of your terms in your factorization (remember negatives!).
A rectangular floor measures by feet, where and are positive integers with . An artist paints a rectangle on the floor with the sides of the rectangle parallel to the sides of the floor. The unpainted part of the floor forms a border of width foot around the painted rectangle and occupies half of the area of the entire floor. How many possibilities are there for the ordered pair ?
The painted rectangle loses foot on each side. What are its dimensions?
Consider the set of all fractions , where and are relatively prime positive integers. How many of these fractions have the property that if both numerator and denominator are increased by , the value of the fraction is increased by ?
For how many integers is the square of an integer?
Grandma has just finished baking a large rectangular pan of brownies. She is planning to make rectangular pieces of equal size and shape, with straight cuts parallel to the sides of the pan. Each cut must be made entirely across the pan. Grandma wants to make the same number of interior pieces as pieces along the perimeter of the pan. What is the greatest possible number of brownies she can produce?
In this section you will be able to factor higher powers, spot Sophie Germain's identity, and watch products telescope.
Is 10⁴ + 324 prime? Write 324 = 4 · 3⁴, and Sophie Germain splits it into 58 × 178.
always has the factor , and for odd , always has the factor . These are Theorem 12.4.1 from Chapter 12.
Sophie Germain’s identity is new: is a sum, yet it factors. It is a difference of squares in disguise, .
Sum of odd powers:
The signs in the second factor alternate between positive and negative.
Difference of powers:
The signs in the second factor are all positive.
Same identities as Theorem 12.4.1.
Multiply by the long factor. Each cancels against the next , so only survives. For odd powers, replace by .
Complete the square: . Now it's a difference of squares: .
Be on the lookout for 4th powers to apply Sophie Germain's Identity!
They can hide: .
What is the remainder when is divided by ?
Compute
In this section you will be able to mix substitution, factoring and number theory on contest problems.
Time to mix it all up. These problems use factorials, digit sums, parity, coins and dice, and each one hides a factorization. Every problem has three hints if you get stuck.
Want every problem from this chapter on one page? Open the problem set.
This problem also appears in the book as 22.1.3.
For all integers , the value of
is always which of the following?
This problem also appears in the book as 24.1.10.
Let equal the sum of the digits of positive integer . For example, . For a particular positive integer , . Which of the following could be the value of ?
This problem also appears in the book as 19.2.6.
When a student multiplied the number by the repeating decimal
where and are digits, he did not notice the notation and just multiplied times . Later he found that his answer is less than the correct answer. What is the 2-digit number ?
A sequence of numbers is defined by , , and for . What are the parities (evenness or oddness) of the triple of numbers , where denotes even and denotes odd?
Let be a function defined on the set of positive rational numbers with the property that for all positive rational numbers and . Suppose that also has the property that for every prime number . For which of the following numbers is ?
Let be the unique function defined on the positive integers such that
for all positive integers , where the sum is taken over all positive divisors of . What is ?
In the state of Coinland, coins have values , , and cents. Suppose is the value in cents of the most expensive item in Coinland that cannot be purchased using these coins with exact change. What is the sum of the digits of ?
When a standard 6-sided die is rolled times, the product of the numbers rolled can be any of possible values. What is ?
Square has sides of length . Points and lie on and , respectively, with and . A path begins along the segment from to and continues by reflecting against the sides of (with congruent incoming and outgoing angles). If the path hits a vertex of the square, it terminates there; otherwise it continues forever. At which vertex does the path terminate?
Three clever monkeys divide a pile of bananas. The first monkey takes some bananas from the pile, keeps three-fourths of them, and divides the rest equally between the other two. The second monkey takes some bananas from the pile, keeps one-fourth of them, and divides the rest equally between the other two. The third monkey takes the remaining bananas from the pile, keeps one-twelfth of them, and divides the rest equally between the other two. Given that each monkey receives a whole number of bananas whenever the bananas are divided, and the numbers of bananas the first, second, and third monkeys have at the end of the process are in the ratio , what is the least possible total for the number of bananas?
The number is expressed in the form
where and are positive integers and is as small as possible. What is ?
For , let , where there are zeros between the and the . Let be the number of factors of in the prime factorization of . What is the maximum value of ?
Two fair dice, each with at least faces, are rolled. On each face of each die is printed a distinct integer from to the number of faces on that die, inclusive. The probability of rolling a sum of is of the probability of rolling a sum of , and the probability of rolling a sum of is . What is the least possible number of faces on the two dice combined?
For how many positive integers less than or equal to is evenly divisible by ?
Let be the set of all perfect squares whose rightmost three digits in base are . Let be the set of all numbers of the form , where is in . In other words, is the set of numbers that result when the last three digits of each number in are truncated. Find the remainder when the tenth smallest element of is divided by .
Find the largest integer satisfying the following conditions:
(i) can be expressed as the difference of two consecutive cubes;
(ii) is a perfect square.