Elementary Number Theory Problems 2.5 Solution (David M. Burton's 7th Edition)

Background

These are my solutions while I was studying number theory using this book. I will use the theorems and definitions mentioned in the book.

If you don't have the book and are not sure which theorem or definition I am using here, you can check this article, where I listed all theorems, corollaries, and definitions by following the book's order.

Theorems and Corollaries in Elementary Number Theory (Ch 1 - 3)

All theorems and corollaries mentioned in David M. Burton’s Elementary Number Theory are listed by following the book’s order. (7th Edition) (Currently Ch 1 - 3)

RanblogRan

If you haven't heard of this book and are interested in learning number theory, I strongly recommend it since it is very friendly for beginners. You can check out the book by this link:

Elementary Number Theory (Paperback)

Get it now:

Also, for my solutions, I will only use theorems or facts that are proved before this chapter. So you will not see that I quote theorems or facts from the later chapters.

Limited-Time Offer: 50% Off Discount Forever!

[This is for the early supporters. You will have 50% Off forever! This offer will last until I finish 10 premium articles.]

All Problems in 2.5 (p. 37)

1. Which of the following Diophantine equations cannot be solved?
   (a) $6x +51y = 22$.
   (b) $33x + 14y = 115$.
   (c) $14x + 35y = 93$.
2. Determine all solutions in the integers of the following Diophantine equations:
   (a) 56x + 72y = 40.
   (b) 24x + 138y = 18.
   (c) 221x + 35y = 11.
3. Determine all solutions in the positive integers of the following Diophantine equations:
   (a) $18x + 5y = 48$.
   (b) $54x + 21y = 906$.
   (c) $123x + 360y = 99$.
   (d) $158x - 57y = 7$.
4. If $a$ and $b$ are relatively prime positive integers, prove that the Diophantine equation $ax - by = c$ has infinitely many solutions in the positive integers.
   [Hint: There exist integers $x_0$ and $y_0$ such that $ax_0 + by_0 = c$. For any integer $t$, which is larger than both $\lvert x_0 \rvert / b$ and $\lvert y_0 \rvert /a$, a positive solution of the given equation is $x = x_0 + bt$, $y =-(y_0 - at)$.]
5. (a) A man has \$4.55 in change composed entirely of dimes and quarters. What are the maximum and minimum number of coins that he can have? Is it possible for the number of dimes to equal the number of quarters?
   (b) The neighborhood theater charges \$1.80 for adult admissions and \$.75 for children. On a particular evening the total receipts were $90. Assuming that more adults than children were present, how many people attended?
   (c) A certain number of sixes and nines is added to give a sum of 126; if the number of sixes and nines is interchanged, the new sum is 114. How many of each were there originally?
6. A farmer purchased $100$ head of livestock for a total cost of $\$4000$. Prices were as follow: calves, $\$120$ each; lambs, $\$50$ each; piglets, $\$25$ each. If the farmer obtained at least one animal of each type, how many of each did he buy?
7. When Mr. Smith cashed a check at his bank, the teller mistook the number of cents for the number of dollars and vice versa. Unaware of this, Mr. Smith spent $68$ cents and then noticed to his surprise that he had twice the amount of the original check. Determine the smallest value for which the check could have been written.
   [Hint: If $x$ denotes the number of dollars and $y$ the number of cents in the check, then $100y + x - 68 = 2(100x + y)$.]
8. Solve each of the puzzle-problems below:
   (a) Alcuin of York, 775. One hundred bushels of grain are distributed among $100$ persons in such a way that each man receives $3$ bushels, each woman $2$ bushels, and each child $\frac{1}{2}$ bushel. How many men, women, and children are there?
   (b) Mahaviracarya, 850. There were $63$ equal piles of plantain fruit put together and $7$ single fruits. They were divided evenly among $23$ travelers. What is the number of fruits in each pile?
   [Hint: Consider the Diophantine equation $63x + 7 = 23y$.]
   (c) Yen Kung, 1372. We have an unknown number of coins. If you make $77$ strings of them, you are $50$ coins short; but if you make $78$ strings, it is exact. How many coins are there?
   [Hint: If $N$ is the number of coins, then $N = 77x + 27 = 78y$ for integers $x$ and $y$.]
   (d) Christoff Rudolff, 1526. Find the number of men, women, and children in a company of $20$ persons if together they pay $20$ coins, each man paying $3$, each woman $2$, and each child $\frac{1}{2}$.
   (e) Euler, 1770. Divide $100$ into two summands such that one is divisible by $7$ and the other by $11$.

My Solutions (Q1 - Q8)

Q1

Which of the following Diophantine equations cannot be solved?

(a) $6x +51y = 22$.
(b) $33x + 14y = 115$.
(c) $14x + 35y = 93$.

(a)

Hence, $gcd(51, 6) = 3$. Because $3 \not \mid 22$, by Theorem 2.9, the equation cannot be solved.

(b)

Hence, $gcd(33, 14) = 1$. Because $1 \mid 115$, By Theorem 2.9, the equation can be solved.

(c)

Hence, $gcd(35, 14) = 7$. Because $7 \not \mid 93$, By Theorem 2.9, the equation cannot be solved.

Q2

Determine all solutions in the integers of the following Diophantine equations:

(a) 56x + 72y = 40.
(b) 24x + 138y = 18.
(c) 221x + 35y = 11.

(a)

Hence, $gcd(72, 56) = 8$. Since $8 \mid 40$, by Theorem 2.9, the equation has a solution. By using the extended Euclidean Algorithm:

Upon multiplying this relation by $5$, we arrive at

Therefore, we get one possible solution where $x = 20$ and $y = -15$.

By using Theorem 2.9, all solutions are:

where $t$ is an integer.

(b)

Hence, $gcd(138, 24) = 6$. Since $6 \mid 18$, by Theorem 2.9, the equation has a solution. By using the extended Euclidean Algorithm:

Upon multiplying this relation by $3$, we arrive at

Therefore, we get one possible solution where $x = 18$ and $y = -3$.

By using Theorem 2.9, all solutions are:

where $t$ is an integer.

(c)

Hence, $gcd(221, 35) = 1$. Since $1 \mid 11$, by Theorem 2.9, the equation has a solution. By using the extended Euclidean Algorithm:

Upon multiplying this relation by $11$, we arrive at

Therefore, we get one possible solution where $x = 176$ and $y = -1111$.

By using Theorem 2.9, all solutions are:

where $t$ is an integer.

Q3

Determine all solutions in the positive integers of the following Diophantine equations:

(a) $18x + 5y = 48$.
(b) $54x + 21y = 906$.
(c) $123x + 360y = 99$.
(d) $158x - 57y = 7$.

(a)

Hence, $gcd(18, 5) = 1$. Since $1 \mid 48$, by Theorem 2.9, the equation has a solution. By using the extended Euclidean Algorithm:

Upon multiplying this relation by $48$, we arrive at

Therefore, we get one possible solution where $x = 96$ and $y = -336$.

By using Theorem 2.9, all solutions are:

where $t$ is an integer.

For solutions in the positive integers, we require $96 + 5t \gt 0$ and $-336 - 18t \gt 0$, which results in $t \gt \frac{-96}{5} (= -19.2)$ and $t \lt \frac{-336}{18} (\approx -18.67)$.

Therefore, $t = -19$. The solution is $x = 96 + 5 \cdot (-19) = 1$ and $y = -336 - 18(-19) = 6$.

(b)

Hence, $gcd(54, 21) = 3$. Since $3 \mid 906$, by Theorem 2.9, the equation has a solution. By using the extended Euclidean Algorithm:

Upon multiplying this relation by $302$, we arrive at

Therefore, we get one possible solution where $x = 604$ and $y = -1510$.

By using Theorem 2.9, all solutions are:

where $t$ is an integer.

For solutions in the positive integers, we require $604 + 7t \gt 0$ and $-1510 - 18t \gt 0$, which results in $t \gt \frac{-604}{7} (\approx -86.29)$ and $t \lt \frac{-1510}{18} (\approx -83.89)$.

Therefore, $t = -84$, $-85$ or $-86$.

For $t = -84$:

For $t = -85$:

For $t = -86$:

These are three positive solutions for the given equation.

(c)

Hence, $gcd(360, 123) = 3$. Since $3 \mid 99$, by Theorem 2.9, the equation has a solution. By using the extended Euclidean Algorithm:

Upon multiplying this relation by $33$, we arrive at

Therefore, we get one possible solution where $x = 1353$ and $y = -462$.

By using Theorem 2.9, all solutions are:

where $t$ is an integer.

For solutions in the positive integers, we require $1353 + 120t \gt 0$ and $-462 - 41t \gt 0$, which results in $t \gt \frac{-1353}{120} (\approx -11.275)$ and $t \lt \frac{-462}{41} (\approx -11.268)$.

Therefore, there are no solutions in the positive integers for the given equation.

(d)

From Section 2.3 Q11, we know $gcd(158, -57) = gcd(158, 57)$.

Hence, $gcd(158, 57) = 1$. Since $1 \mid 7$, by Theorem 2.9, the equation has a solution. By using the extended Euclidean Algorithm:

Upon multiplying this relation by $7$, we arrive at

Therefore, we get one possible solution where $x = -154$ and $y = -427$.

By using Theorem 2.9, all solutions are:

where $t$ is an integer.

For solutions in the positive integers, we require $-154 - 57t \gt 0$ and $-427 - 158t \gt 0$, which results in $t \lt \frac{-154}{57} (\approx -2.70)$ and $t \lt \frac{-427}{158} (\approx -2.70)$.

Therefore, the solutions in the positive integers will be $x = -154 - 57t$ and $y = -427 - 158t$ when $t \leq -3$.

Q4

If $a$ and $b$ are relatively prime positive integers, prove that the Diophantine equation $ax - by = c$ has infinitely many solutions in the positive integers.
[Hint: There exist integers $x_0$ and $y_0$ such that $ax_0 + by_0 = c$. For any integer $t$, which is larger than both $\lvert x_0 \rvert / b$ and $\lvert y_0 \rvert /a$, a positive solution of the given equation is $x = x_0 + bt$, $y =-(y_0 - at)$.]

Because $gcd(a, b) = 1 \mid c$, by Theorem 2.9, $ax + by = c$ has a solution.

Let $x_0$ and $y_0$ be a particular solution for $ax + by = c$. By corollary of 2.9, we have $x = x_0 + bt$ and $y = y_0 - at$ for $ax + by = c$.

For $ax - by = c$, the solutions will then be $x = x_0 + bt$ and $y = -(y_0 - at)$.

For solutions in positive integers, we require $x_0 + bt \gt 0$ and $-(y_0 - at) \gt 0$, which results in $t \gt \frac{-x_0}{b}$ and $t \gt \frac{y_0}{a}$.

We don't know which one of $\frac{-x_0}{b}$ and $\frac{y_0}{a}$ is larger when $x_0$ and $y_0$ are having opposite signs. Therefore, $t$ has to be larger than both $\frac{\lvert x_0 \rvert}{b}$ and $\frac{\lvert y_0 \rvert}{a}$.

Therefore, when $t$ is larger than both $\frac{\lvert x_0 \rvert}{b}$ and $\frac{\lvert y_0 \rvert}{a}$, $ax - by = c$ has infinitely many solutions in the positive solutions given by $x = x_0 + bt$ and $y = -(y_0 - at)$.

Q5

(a) A man has \$4.55 in change composed entirely of dimes and quarters. What are the maximum and minimum number of coins that he can have? Is it possible for the number of dimes to equal the number of quarters?
(b) The neighborhood theater charges \$1.80 for adult admissions and \$.75 for children. On a particular evening the total receipts were $90. Assuming that more adults than children were present, how many people attended?
(c) A certain number of sixes and nines is added to give a sum of 126; if the number of sixes and nines is interchanged, the new sum is 114. How many of each were there originally?

(a)

Let $x$ and $y$ be the number of dimes and the number of quarters, respectively. From the description, we assume $x \gt 0$ and $y \gt 0$.

We have the Diophantine equation: $0.1x + 0.25y = 4.55$, which can be simplified into $2x + 5y = 91$.

Because $gcd(2, 5) = 1 \mid 91$, by Theorem 2.9, the equation has a solution.

We know $2(-2) + 5(1) = 1$. By multiplying $91$ on both sides, we get $2(-182) + 5(91) = 91$. By Theorem 2.9, all solutions are given by:

where $t$ is an integer.

Because $x$ and $y$ must be greater than $0$, we require $-182 + 5t \gt 0$ and $91 - 2t \gt 0$, which results in $t \gt \frac{182}{5} (\approx 36.4)$ and $t \lt \frac{91}{2} (= 45.5)$. Therefore, $t = 37$, $38$, ... , or $45$.

The total number of coins will be $x + y = -182 + 5t + 91 - 2t = 3t - 91$. The maximum number of coins will be $3(45) - 91 = 44$. The minimum number of coins will be $3(37) - 91 = 20$.

When $-182 + 5t = 91 - 2t$, $t = 39$ and $x = y = 91 - 2(39) = 13$. Therefore, it is possible that the number of dimes equals the number of quarters. The number will be $13$ for each type.

(b)

Let $x$ and $y$ be the number of adults and the number of children, respectively. From the description, we assume $x \gt 0$ and $y \geq 0$.

We have the Diophantine equation: $1.8x + 0.75y = 90$, which can be simplified into $12x + 5y = 600$.

Because $gcd(12, 5) = 1 \mid 600$, by Theorem 2.9, the equation has a solution.

We know $12(-2) + 5(5) = 1$ by observation. By multiplying $600$ on both sides, we get $12(-1200) + 5(3000) = 600$. By Theorem 2.9, all solutions are given by:

where $t$ is an integer.

We require $-1200 + 5t \gt 0$ and $3000 - 12t \geq 0$, which results in $t \gt 240$ and $t \leq 250$. Also, $x > y$ means $-1200 + 5t \gt 3000 -12t$, which results in $t \gt \frac{4200}{17} (\approx 247.06)$. Therefore, $t = 248$, $249$, or $250$.

The total number of people attended will be $x + y = -1200 + 5t + 3000 - 12t = 1800 - 7t$. Therefore, $1800 - 7t = 64$, $57$ or $50$ when $t = 248$, $249$ or $250$.

The total number of people attended is $64$, $57$, or $50$.

(c)

Let $x$ and $y$ be the number of sixes and nines, respectively.

From the description, we have the equation $6x + 9y = 126$ and $6y + 9x = 114$. You may have the intention to do it as the Diophantine equation. Well, don't do that😂.

You can just solve it as systems of linear equations. We get $36x + 54y = 756$ and $24y + 36x = 456$ from the original equations. Solving gives $y = 10$ and $x = 6$.

Therefore, there are $6$ sixes and $10$ nines.

Q6

A farmer purchased $100$ head of livestock for a total cost of $\$4000$. Prices were as follow: calves, $\$120$ each; lambs, $\$50$ each; piglets, $\$25$ each. If the farmer obtained at least one animal of each type, how many of each did he buy?

From the description, we have $120x + 50y + 25z = 4000$ and $x + y + z = 100$ where $x \geq 1$, $y \geq 1$ and $z \geq 1$.

By substituting $z$ with $100 - x - y$ in the first equation, we get $120x + 50y + 25(100 - x - y) = 4000$. After simplification, we get $19x + 5y = 300$.

Because $gcd(19, 5) = 1 \mid 300$, by Theorem 2.9, the equation has a solution.

We know $19(-1) + 5(4) = 1$ by observation. By multiplying $300$ on both sides, we get $19(-300) + 5(1200) = 300$. By Theorem 2.9, all solutions are given by:

where $t$ is an integer.

Hence, $z = 100 - x - y = -800 + 14t$.

We require $-300 + 5t \geq 1$, $1200 - 19t \geq 1$, and $-800 + 14t \geq 1$, which results in $t \geq \frac{301}{5} (\approx 60.2)$, $t \leq \frac{1199}{19} (\approx 63.11)$ and $t \geq \frac{801}{14} (\approx 57.21)$. Therefore, $t = 61$, $62$, or $63$.

When $t = 61$, $x = 5$, $y = 41$, and $z = 54$.
When $t = 62$, $x = 10$, $y = 22$, and $z = 68$.
When $t = 63$, $x = 15$, $y = 3$, and $z = 82$.

Q7

When Mr. Smith cashed a check at his bank, the teller mistook the number of cents for the number of dollars and vice versa. Unaware of this, Mr. Smith spent $68$ cents and then noticed to his surprise that he had twice the amount of the original check. Determine the smallest value for which the check could have been written. [Hint: If $x$ denotes the number of dollars and $y$ the number of cents in the check, then $100y + x - 68 = 2(100x + y)$.]

Let $x$ and $y$ be the number of dollars and the number of cents, respectively.

From the description, we get the equation $100y + x - 68 = 2(100x + y)$ where $x \gt 0$ and $y \gt 0$.

By Section 2.3 Q11, we know $gcd(-199, 98) = gcd(199, 98)$. By using Euclidean Algorithm:

Thus $gcd(199, 98) = 1 \mid 68$, by Theorem 2.9, the equation has a solution.

By using Extended Euclidean Algorithm:

By multiplying $68$ on both sides, we get $199(2244) + 98(-4556) =68$. Hence, $-199(2244) + 98(-4556) = 68$. By Theorem 2.9, all solutions are given by:

where $t$ is an integer.

We require $-2244 + 98t \gt 0$ and $-4556 + 199t \gt 0$, which results in $t \gt \frac{1122}{49} (\approx 22.90)$ and $t \gt \frac{4556}{199} (\approx 22.89)$.

The original check would be $100x + y = 100(-2244 + 98t) + (-4556 + 199t) = 9999t -228956$. As $100y + x - 68 = 2(100x + y)$, the left-hand side will reach the smallest value as $100x + y$ reaches its smallest value. $100x + y$ will reach its smallest value when $t = 23$.

Therefore, the original check is $9999(23) - 228956 = 1021$, which is $10$ dollars and $21$ cents. The check that could have been written is $21$ dollars and $10$ cents.

Q8

Solve each of the puzzle-problems below:

(a) Alcuin of York, 775. One hundred bushels of grain are distributed among $100$ persons in such a way that each man receives $3$ bushels, each woman $2$ bushels, and each child $\frac{1}{2}$ bushel. How many men, women, and children are there?
(b) Mahaviracarya, 850. There were $63$ equal piles of plantain fruit put together and $7$ single fruits. They were divided evenly among $23$ travelers. What is the number of fruits in each pile?
[Hint: Consider the Diophantine equation $63x + 7 = 23y$.]
(c) Yen Kung, 1372. We have an unknown number of coins. If you make $77$ strings of them, you are $50$ coins short; but if you make $78$ strings, it is exact. How many coins are there?
[Hint: If $N$ is the number of coins, then $N = 77x + 27 = 78y$ for integers $x$ and $y$.]
(d) Christoff Rudolff, 1526. Find the number of men, women, and children in a company of $20$ persons if together they pay $20$ coins, each man paying $3$, each woman $2$, and each child $\frac{1}{2}$.
(e) Euler, 1770. Divide $100$ into two summands such that one is divisible by $7$ and the other by $11$.

(a)

Let $x$, $y$, and $z$ be the number of men, women, and children, respectively.

From the description, we get the equation $3x + 2y + \frac{1}{2}z = 100$ and $x + y + z = 100$. We assume $x \geq 0$, $y \geq 0$, and $z \geq 0$.

By substituting $z$ with $100 - x - y$ in the first equation, we get:

Because $gcd(5, 3) = 1 \mid 100$, by Theorem 2.9, the equation has a solution.

From observation, we have $5(20) + 3(0) = 100$. By Theorem 2.9, all solutions are given by:

where $t$ is an integer.

Hence, $z = 100 - (x + y) = 100 - (20 - 2t) = 80 + 2t$.

We require $20 + 3t \geq 0$, $- 5t \geq 0$, and $80 + 2t \geq 0$, which results in $t \geq \frac{-20}{3} (\approx -6.67)$, $t \leq 0$ and $t \geq -40$. Therefore, $t = -6$, $-5$,..., or $0$.

When $t = -6$, $2$ men, $30$ women, and $68$ children are there.
When $t = -5$, $5$ men, $25$ women, and $70$ children are there.
When $t = -4$, $8$ men, $20$ women, and $72$ children are there.
When $t = -3$, $11$ men, $15$ women, and $74$ children are there.
When $t = -2$, $14$ men, $10$ women, and $76$ children are there.
When $t = -1$, $17$ men, $5$ women, and $78$ children are there.
When $t = 0$, $20$ men, $0$ women, and $80$ children are there.

(b)

Let $x$ and $y$ be the number of fruits in a pile of plantain and the number of fruits for each traveler, respectively.

From the description, we get the equation $63x + 7 =23y$ where $x \gt 0$ and $y \gt 0$.

Considering the form $63x - 23y = -7$, from Section 2.3 Q11, we know $gcd(63, -23) = gcd(63, 23)$. By using Euclidean Algorithm:

Thus $gcd(63, 23) = 1 \mid -7$. By Theorem 2.9, the equation has a solution. Using Extended Euclidean Algorithm:

We multiply both sides by $-7$ and get $63(28) + 23(-77) = -7$. Hence, $63(28) + (-23)(77) = -7$. By Theorem 2.9, all solutions are given by:

where $t$ is an integer.

We require $28 + (-23)t \gt 0$ and $77 - 63t \gt 0$, which results in $t \lt \frac{28}{23} (\approx 1.22)$ and $t \lt \frac{77}{63}$. Therefore, $t = 0$ or $1$.

When $t = 0$, $28$ fruits are in a pile of plantain and $77$ fruits are for each traveler.
When $t = 1$, $5$ fruits are in a pile of plantain and $14$ fruits are for each traveler.

(c)

First, let $y$ be the number of coins in one string if we make $78$ strings.

Some people may think the hint is wrong, but it is actually correct. It depends on how we define $x$.

If we define $x$ as the number of coins in one string if we make $77$ strings. The equation will be $77x - 50 = 78y$. This way, we consider filling up as many strings as possible first.

Another way is to separate all the coins into $77$ strings until we run out of coins (like dealing cards to players one by one). Then the first $27$ strings will have $1$ extra coin. We define the $x$ as the number of coins in the common part. The equation will be $77x + 27 = 78y$, like the one shown in the hint.

Both equations will give you the same answer. Let's go with the second equation. We also know $x \gt 0$, $y \gt 0$, and $x + 1 \gt y$.

Considering the form $77x - 78y = -27$, from Section 2.3 Q11, we know $gcd(77, -78) = gcd(77, 78) = 1$. Because $1 \mid -27$, by Theorem 2.9, the equation has a solution.

By observation, $77(-1) - 78(-1) = 1$. We multiply both sides by $-27$. We get $77(27) - 78(27) = -27$. By Theorem 2.9, all solutions are given by:

where $t$ is an integer.

We require $27 - 78t \gt 0$, $27 - 77t \gt 0$ and $27 -78t + 1 \gt 27 - 77t$, which results in $t \lt \frac{27}{78} (\approx 0.35)$, $t \lt \frac{27}{77} (\approx 0.35)$, and $t \lt 1$. Therefore, $t \leq 0$.

The total number of coins will be $78(27 - 77t) = 2106 - 6006t$ where $t \leq 0$. The smallest possibility will be $2106$ coins.

(d)

Let $x$, $y$, and $z$ be the number of men, number of women, and number of children, respectively.

From the description, we get the equation $3x + 2y + \frac{1}{2}z = 20$ and $x + y + z = 20$. We assume $x \geq 0$, $y \geq 0$ and $z \geq 0$.

By substituting $z$ with $20 - x - y$ in the first equation, we get:

Because $gcd(5, 3) = 1 \mid 20$, by Theorem 2.9, the equation has a solution.

By observation, $5(4) + 3(0) = 20$. Therefore, by Theorem 2.9, all solutions are given by:

where $t$ is an integer.

Hence, $z = 20 - (x + y) = 20 - (4 - 2t) = 16 + 2t$.

We require $4 + 3t \geq 0$, $-5t \geq 0$ and $16 + 2t \geq 0$, which results in $t \geq \frac{-4}{3} (\approx -1.33)$, $t \leq 0$ and $t \geq -8$. Therefore, $t = 0$ or $1$.

When $t = 0$, there are $4$ men, $0$ women, and $16$ children.
When $t = -1$, there are $1$ man, $5$ women, and $14$ children.

(e)

Let $m$ and $n$ be the two summands, respectively. WLOG, we assume $7 \mid m$ and $11 \mid n$. Then $m = 7x$ and $n = 11y$ for some integers $x$ and $y$. Thus we have the equation $7x + 11y = 100$.

Because $gcd(7, 11) = 1 \mid 100$, by Theorem 2.9, the equation has a solution.

By observation, $7(8) + 11(4) = 100$. Hence, by Theorem 2.9, all the solutions are given by:

where $t$ is an integer.