THEORY OF NUMBERS
HOMEWORK 3 SOLUTIONS
Computations
(1) Use the Chinese remainder theorem to find a solution to each of the following linear
systems:
(a)
x1
x2
x3
mod 2
mod 3
mod 5
x0
x0
x1
x6
mod
mod
mod
mod
2
3
5
7
x2
x3
x4
x5
x6
mod
mod
mod
mod
mod
11
12
13
17
19
(b)
(c)
Solution:
(a) In this problem, the following constants are used in the Chinese remainder theorem
a1 = 1
a2 = 2
a3 = 3
M = 2 3 5 = 30
M1 = 15
M2 = 10
M3 = 6
y1 = 1
y2 = 1
y3 = 1
We get the yis because they should be the inverses of the Mi s. In particular,
M1 1 mod 2, M2 1 mod 3, and M3 1 mod 5. Therefore, a solution to
this congruence is x = a1 M1 y1 +a2 M2 y2 +a3 M3 y3 = 1151+2101+361 = 53.
Since solutions are equivalent mod 30, 23 is also a solution.
1
(b) In this problem, the following constants are used in the Chinese remainder theorem
a1
a2
a3
a4
=0
=0
=1
=6
M = 2 3 5 7 = 210
M1 = 105
M2 = 70
M3 = 42
M4 = 30
y1
y2
y3
y4
=1
=1
=3
=4
We get the yis because they should be the inverses of the Mi s. In particular,
M1 1 mod 2, M2 1 mod 3, M3 2 mod 5, and M4 2 mod 7. Therefore, a solution to this congruence is x = a1 M1 y1 + a2 M2 y2 + a3 M3 y3 + a4 M4 y4 =
0 105 1 + 0 70 1 + 1 42 3 + 6 30 4 = 846. Since solutions are equivalent
mod 210, 6 is also a solution.
(c) In this problem, the following constants are used in the Chinese remainder theorem
a1
a2
a3
a4
a5
=2
=3
=4
=5
=6
M = 11 12 13 17 19 = 554, 268
M1 = 50, 388
M2 = 46, 189
M3 = 42, 636
M4 = 32, 604
M5 = 29, 172
y1
y2
y3
y4
y5
=7
=1
=3
=8
= 11
We get the yis because they should be the inverses of the Mi s. In particular,
M1 8 mod 11, M2 1 mod 12, M3 9 mod 13, M4 15 mod 17, and
M5 7 mod 19. Therefore, a solution to this congruence is x = a1 M1 y1 +
a2 M2 y2 + a3 M3 y3 + a4 M4 y4 + a5 M5 y5 = 2 50, 388 7 + 3 46, 189 1 + 4 42, 636
3 + 5 32, 604 8 + 6 29, 172 11 = 4, 585, 143. Since solutions are equivalent
mod 554, 268, 105, 999 is also a solution.
(2) Find all invertible elements for n = 11, , 20. You do not need to find the inverses,
you only need to write down which elements are invertible.
Hint: There is an easier way than writing down a large multiplication table (although
that would work).
Solution: We showed in class that a a is invertible mod m if gcd(a, m) = 1.
Therefore, all we have to do is to find elements which are relatively prime to n for
the various choices of n. These elements are
11 :1, 2, 3, 4, 5, 6, 7, 8, 9, 10
13 :1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12
15 :1, 2, 4, 7, 8, 11, 13, 14
17 :1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16
19 :1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18
12 :1, 5, 7, 11
14 :1, 3, 5, 9, 11, 13
16 :1, 3, 5, 7, 9, 11, 13, 15
18 :1, 5, 7, 11, 13, 17
20 :1, 3, 7, 9, 11, 13, 17, 19
(3) For each of the following linear Diophantine equations, find a solution or show that
none exists.
2
(a) 3x + 4y = 7
(b) 60x + 18y = 97
(c) 25x + 95y = 970.
Solution:
(a) We first compute the gcd of 3, 4. Using the Euclidean algorithm, we find
4= 13+1
3= 31+0
Therefore, 1 is the gcd(3, 4), and considering the first line, we have that 413 =
1. Since 1|7, this equation has solutions. One solution can be given by mutiplying
through by 7 to get 7 4 7 3 = 7, so letting x = 7 and y = 7 gives the result.
In fact, all solutions are of the form x = 7 4k and y = 7 + 3k.
(b) We first compute the gcd of 60, 18. Using the Euclidean algorithm, we find
60 = 3 18 + 6
18 = 3 6 + 0
Therefore, 6 is the gcd(18, 60), and since 6 97, this congruence has no solutions
in the integers.
(c) We first compute the gcd of 25, 95. Using the Euclidean algorithm, we find
95 = 3 25 + 20
25 = 1 20 + 5
20 = 4 5 + 0
Therefore, 5 is the gcd(25, 95), and by considering the Euclidean algorithm in
the opposite direction we have 5 = 25 1 20 and 20 = 95 3 25. Substituting
in gives 5 = 4 25 1 95. Since 5|970, this equation has solutions. One solution
can be given by multiplying through by 970/5 = 194 to get 5 = 776 25 194 95,
so letting x = 776 and y = 194 gives the result. In fact, all solutions are of the
form x = 776 + 19k and y = 194 5k.
Proofs
(4) Prove the following results about gcds
(a) Show that if k is a positive integer, then 3k + 2 and 5k + 3 are relatively prime.
Hint: On this one, you should just apply the Euclidean algorithm, the only
place you need to be careful is to make sure that the remainder is in the right
range. If k is large, this is not a problem. If k is smaller, you may need to be
careful.
(b) Show that if a and b are relatively prime integers, then gcd(a + 2b, 2a + b) is
either 1 or 3.
Hint: This one is slightly more difficult than the previous problems, as a first
step, why can we assume a b?
Solution:
(a) On this one, lets try to apply the Euclidean algorithm. The first step in the
algorithm is 5k + 3 = (3k + 2) + (2k + 1). Now, we must check that 0 2k + 1 <
3k + 2. Since k is positive, the first inequality holds, and the other inequality
holds because 3k + 2 = (2k + 1) + (k + 1) and k + 1 > 0 since k is positive. The
3
next step of the Euclidean algorithm is 3k + 2 = 1(2k + 1) + (k + 1). Now, we
must check that 0 k + 1 < 2k + 1. Since k is positive, the first inequality holds,
and the other inequality holds because 2k + 1 = (k + 1) + k and k > 0 since k is
positive. The next step of the Euclidean algorithm is 2k + 1 = (k + 1) + k. Now,
we must check that 0 k < k + 1. Since k is positive, the first inequality holds
and since 1 > 0, the second inequality holds. The next step of the Euclidean
algorithm is k + 1 = k + 1. Now, we must check that 0 1 < k, the first
inequality is true and the second inequality holds for k > 1. At this point, we
must split the argument into cases, where k 2 and where k = 1.
Assume first that k 2, then the above argument is a step in the Euclidean
algorithm and the last step in the Euclidean algorithm is k = k 1 + 0, which
implies that the gcd is 1.
Assume now that k = 1, then we must redo the last step of the Euclidean
algorithm. In particular, k + 1 = 2 and k = 1 so the final step of the Eucildean
algorithm is k + 1 = 2 k + 0. Therefore, the gcd is k, which is 1. Therefore,
5k + 3 and 3k + 2 are relatively prime.
(b) Note that if g = gcd(a+2b, 2a+b), then g divides all linear combinations of these
sums by a previous homework problem. Therefore g|2(2a + b) (a + 2b) = 3a
and g|2(a + 2b) (2a + b) = 3b. Therefore, g| gcd(3a, 3b). Since both a and b are
multiplied by 3, we have g|3 gcd(a, b) = 3. Since g|3 and g is positive, g = 1, 3.
(5) Show that the system of congruences
x a1
x a2
mod m1
mod m2
has a solution if and only if gcd(m1 , m2 )|(a1 a2 ).
Hint: It may be the case that gcd(m1 , m2 ) 6= 1. Use the first congruence to write
x = a1 + km1 and plug this into the second congruence and then use a result from
class.
Solution: Assume first that there is a solution x, then x a1 mod m1 , so m1 |xa1
and therefore, there exists some k such that km1 = x a1 or that x = a1 + km1 .
On the other hand, x a2 mod m2 , so m3 |x a2 and therefore, there exists some l
such that lm2 = x a2 or that x = a2 + lm2 . Setting these two equal to one another
we find that a1 + km1 = a2 + lm2 and, after some rearranging, a1 a2 = lm2 km1 .
Since the RHS is a linear combination of m1 and m2 , it follows from a result in class
that it is a multiple of gcd(m1 , m2 ). Let d = gcd(m1 , m2 ), then there exists a j such
that a1 a2 = jd and so k|a1 a2 .
Now, assume otherwise that gcd(m1 , m2 )|a1 a2 . Therefore, a1 a2 is a multiple
of the gcd and there exist y, z such that m1 y + m2 z = a1 a2 . Now, by rearranging,
we find that a1 m1 y = a2 + m2 z and let this be x. Now, x a1 mod m1 since
x a1 = m1 y and so m1 |x a1 . Similarly, x a2 mod m2 since x a2 = m2 z and
so m2 |x a2 .
Challenge
4
(6) Find an integer solution (if one exists) to the following system of linear Diophantine
equations.
x + y + z + w = 100
x + 2y + 3z + 4w = 300
x + 4y + 9z + 16w = 1000
Solution: The easiest way to do this problem is to use linear algebra. Using linear
algebra, we find that w is a free parmeter and the solution is as follows:
x = 50 w
y = 100 + 3w
z = 150 3w
Now, for this to be a number theory solution, all of these variables should be integers
(whereas real or complex numbers in linear algebra). Therefore, w must be an integer.
When w is an integer, the equations give x, y, z as integers as well, so this describes
all solutions. In particular, one solution is (50, 100, 150, 0).