1.5#
Exercises from Humphreys, J. F. & M. Y. Prest. (2008). Numbers, Groups, and Codes. 2nd Ed. Cambridge University Press.
1#
Find all the solutions (when there are any) of the following linear congruences.
\( \begin{aligned} 3x &\equiv 1& \mod && 12 &\quad \text{no solution} \\ 3x &\equiv 1& \mod && 11 &\quad [4]_{11} \\ 64x &\equiv 32& \mod && 84 &\quad [11]_{21} \quad\text{or}\quad [11]_{84}, [32]_{84}, [53]_{84}, [74]_{84} \\ 15x &\equiv 5& \mod && 17 &\quad [6]_{17} \\ 15x &\equiv 5& \mod && 18 &\quad \text{no solution} \\ 15x &\equiv 5& \mod && 100 &\quad [7]_{20} \quad\text{or}\quad [7]_{100}, [27]_{100}, [47]_{100}, [67]_{100}, [87]_{100} \\ 23x &\equiv 16& \mod && 107 &\quad [10]_{107} \\ \end {aligned} \)
\(3x \equiv 1 \mod 12\)
\(gcd(3, 12) = 3\) but there are no solutions since \(3 \nmid 1\).
\(3x \equiv 1 \mod 11\)
\(gcd(3, 11) = 1\) and so there is \(1\) solution since \(1 \mid 1\).
\(3x \equiv 1 \mod 11 \iff x = \frac{11(k = 1) + 1}{3} = 4\)
\([4]_{11}\)
print(3*4 % 11)
1
\(64x \equiv 32 \mod 84\)
\( \begin{aligned} 64 &= 2^6 \\ 84 &= 2^2 \times 3 \times 7 \\ gcd(64, 84) &= 2^2 \\ \end {aligned} \)
\(gcd(64, 84) = 4\) and so there are \(4\) solutions modulo \(84\) since \(4 \mid 32\).
\(\frac{64}{4} x \equiv \frac{32}{4} \mod \frac{84}{4} \iff 16x \equiv 8 \mod 21\)
\(gcd(16, 21) = 1\) and so there is \(1\) solution modulo \(21\) since \(1 \mid 8\).
\(16x \equiv 1 \mod 21 \iff x = \frac{21(k = 3) + 1}{16} = 4\)
\(4 \times 16x \equiv 4 \times 8 = 32 \mod 21 \iff x \equiv 11 \mod 21\)
\([11]_{21}\) or \([11]_{84}, [32]_{84}, [53]_{84}, [74]_{84}\)
a, n = 64, 84
print(a*11 % n)
print(a*32 % n)
print(a*53 % n)
print(a*74 % n)
32
32
32
32
\(15x \equiv 5 \mod 17\)
\(gcd(15, 17) = 1\) and so there is \(1\) solution since \(1 \mid 5\).
\(15x \equiv 1 \mod 17 \iff x = \frac{17(k = 7) + 1}{15} = 8\)
\(8 \times 15x \equiv 8 \times 5 = 40 \mod 17 \iff x \equiv 6 \mod 17\)
\([6]_{17}\)
print(15*6 % 17)
5
\(15x \equiv 5 \mod 18\)
\(gcd(15, 18) = 3\) but there are no solutions since \(3 \nmid 5\).
\(15x \equiv 5 \mod 100\)
\(gcd(15, 100) = 5\) and so there are \(5\) solutions modulo \(100\) since \(5 \mid 5\).
\(\frac{15}{5} x \equiv \frac{5}{5} \mod \frac{100}{5} \iff 3x \equiv 1 \mod 20\)
\(gcd(3, 20) = 1\) and so there is \(1\) solution modulo \(20\) since \(1 \mid 1\).
\(3x \equiv 1 \mod 20 \iff x = \frac{20(k = 1) + 1}{3} = 7\)
\(7 \times 3x \equiv 7 \times 1 \mod 20 \iff x \equiv 7 \mod 20\)
\([7]_{20}\) or \([7]_{100}, [27]_{100}, [47]_{100}, [67]_{100}, [87]_{100}\)
a, n = 15, 100
print(a* 7 % n)
print(a*27 % n)
print(a*47 % n)
print(a*67 % n)
print(a*87 % n)
5
5
5
5
5
\(23x \equiv 16 \mod 107\)
\(gcd(23, 107) = 1\) and so there is \(1\) solution since \(1 \mid 16\).
\(23x \equiv 1 \mod 107 \iff x = \frac{107(k = 3) + 1}{23} = 14\)
\(14 \times 23x \equiv 14 \times 16 = 224 \mod 107 \iff x \equiv 10 \mod 107\)
\([10]_{107}\)
print(23*10 % 107)
16
2#
Solve the following sets of simultaneous linear congruences.
\( \begin{aligned} x &\equiv 4 \mod 24 \\ x &\equiv 7 \mod 11 \\ \end {aligned} \)
\( \begin{aligned} 3x &\equiv 1 \mod 5 \\ 2x &\equiv 6 \mod 8 \\ \end {aligned} \)
\( \begin{aligned} x &\equiv 3 \mod 5 \\ 2x &\equiv 1 \mod 7 \\ x &\equiv 3 \mod 8 \\ \end {aligned} \)
Is there an integer whose remainder is \(4\) when divided by \(24\) and \(7\) when divided by \(11\)?
\( \begin{aligned} x &\equiv 4 \mod 24 \\ x &\equiv 7 \mod 11 \\ \end {aligned} \)
The moduli are pairwise relative primes: \(gcd(24, 11) = 1\).
\( \left ( \begin{array}{cc|c} 1 & 0 & 24 \\ 0 & 1 & 11 \\ \end {array} \right) \to \left ( \begin{array}{cc|c} 1 & -2 & 2 \\ 0 & 1 & 11 \\ \end {array} \right) \to \left ( \begin{array}{cc|c} 1 & -2 & 2 \\ -5 & 11 & 1 \\ \end {array} \right) \)
\(\underset{b}{7} \times \underset{m}{24} \times \underset{k}{(-5)} + \underset{a}{4} \times \underset{n}{11} \times \underset{t}{11} = \underset{c}{-356} \equiv 172 \mod \underset{m}{24} \times \underset{n}{11} = 264\)
\([172]_{264}\)
a = 4
b = 7
m = 24
n = 11
k = -5
t = 11
c = 172
print( m*k + n*t)
print((b*m*k + a*n*t) % (m*n))
print(c % m)
print(c % n)
1
172
4
7
Is there an integer whose remainder is \(1\) when tripled and then divided by \(5\) and \(6\) when doubled and then divided by \(8\)?
\( \begin{aligned} 3x &\equiv 1 \mod 5 \iff x = \frac{5(k = 1) + 1}{3} = 2 \iff x \equiv 2 \mod 5 \\ 2x &\equiv 6 \mod 8 \iff x = \frac{8(k = 1) + 6}{2} = 7 \iff x \equiv 7 \mod 8\\ \end {aligned} \)
The moduli are pairwise relative primes: \(gcd(5, 8) = 1\).
\( \left ( \begin{array}{cc|c} 1 & 0 & 5 \\ 0 & 1 & 8 \\ \end {array} \right) \to \left ( \begin{array}{cc|c} 1 & 0 & 5 \\ -1 & 1 & 3 \\ \end {array} \right) \to \left ( \begin{array}{cc|c} 2 & -1 & 2 \\ -1 & 1 & 3 \\ \end {array} \right) \to \left ( \begin{array}{cc|c} 2 & -1 & 2 \\ -3 & 2 & 1 \\ \end {array} \right) \)
\( \underset{b}{7} \times \underset{m}{5} \times \underset{k}{(-3)} + \underset{a}{2} \times \underset{n}{8} \times \underset{t}{2} = \underset{c}{-73} \equiv 7 \mod \underset{m}{5} \times \underset{n}{8} = 40\)
\([7]_{40}\)
a = 2
b = 7
m = 5
n = 8
k = -3
t = 2
c = 7
print( m*k + n*t)
print((b*m*k + a*n*t) % (m*n))
print(3*c % m)
print( c % m)
print(2*c % n)
print( c % n)
1
7
1
2
6
7
Is there an integer whose remainder is \(3\) when divided by \(5\); \(1\) when doubled and then divided by \(7\); and \(3\) when divided by \(8\)?
\( \begin{aligned} x &\equiv 3 \mod 5 \\ 2x &\equiv 1 \mod 7 \iff x = \frac{7(k = 1) + 1}{2} = 4 \iff x \equiv 4 \mod 7 \\ x &\equiv 3 \mod 8 \\ \end {aligned} \)
The system of linear congruences becomes
\( \begin{aligned} x &\equiv 3 \mod 5 \\ x &\equiv 4 \mod 7 \\ x &\equiv 3 \mod 8 \\ \end {aligned} \)
The moduli are pairwise relative primes: \(gcd(5, 7) = 1 = gcd(5, 8) = gcd(7, 8)\).
\( \left ( \begin{array}{cc|c} 1 & 0 & 5 \\ 0 & 1 & 7 \\ \end {array} \right) \to \left ( \begin{array}{cc|c} 1 & 0 & 5 \\ -1 & 1 & 2 \\ \end {array} \right) \to \left ( \begin{array}{cc|c} 3 & -2 & 1 \\ -1 & 1 & 2 \\ \end {array} \right) \)
\( \underset{b}{4} \times \underset{m}{5} \times \underset{k}{3} + \underset{a}{3} \times \underset{n}{7} \times \underset{t}{(-2)} = \underset{c}{18} \mod \underset{m}{5} \times \underset{n}{7} = 35 \)
The system of linear congruences becomes
\( \begin{aligned} x &\equiv& 18 &\mod& 35 \\ x &\equiv& 3 &\mod& 8 \\ \end {aligned} \)
\( \left ( \begin{array}{cc|c} 1 & 0 & 35 \\ 0 & 1 & 8 \\ \end {array} \right) \to \left ( \begin{array}{cc|c} 1 & -4 & 3 \\ 0 & 1 & 8 \\ \end {array} \right) \to \left ( \begin{array}{cc|c} 1 & -4 & 3 \\ -2 & 9 & 2 \\ \end {array} \right) \to \left ( \begin{array}{cc|c} 3 & -13 & 1 \\ -2 & 9 & 2 \\ \end {array} \right) \)
\( \underset{b}{3} \times \underset{m}{35} \times \underset{k}{3} + \underset{a}{18} \times \underset{n}{8} \times \underset{t}{(-13)} = \underset{c}{-1557} \equiv 123 \mod 280 = \underset{m}{35} \times \underset{n}{8} \)
\([123]_{280}\)
a = 18
b = 3
m = 35
n = 8
k = 3
t = -13
c = 123
print( m*k + n*t)
print((b*m*k + a*n*t) % (m*n))
print( c % m)
print( c % n)
print( c % 5)
print( c % 7)
print(2*c % 7)
print( c % 8)
1
123
18
3
3
4
1
3
3#
Find the smallest positive integer whose remainder when divided by \(11\) is \(8\), which has last digit \(4\) and is divisible by \(27\).
\( \begin{aligned} x &\equiv 8 \mod 11 \\ x &\equiv 4 \mod 10 \\ x &\equiv 0 \mod 27 \\ \end {aligned} \)
The moduli are pairwise relative primes: \(gcd(11, 10) = 1 = gcd(11, 27) = gcd(10, 27)\).
\( \left ( \begin{array}{cc|c} 1 & 0 & 11 \\ 0 & 1 & 10 \\ \end {array} \right) \to \left ( \begin{array}{cc|c} 1 & -1 & 1 \\ 0 & 1 & 10 \\ \end {array} \right) \)
\( \underset{b}{4} \times \underset{m}{11} \times \underset{k}{1} + \underset{a}{8} \times \underset{n}{10} \times \underset{t}{(-1)} = \underset{c}{-36} \equiv 74 \mod \underset{mn}{110} \)
The system of linear congruences becomes
\( \begin{aligned} x &\equiv& 74 &\mod& 110 \\ x &\equiv& 0 &\mod& 27 \\ \end {aligned} \)
\( \left ( \begin{array}{cc|c} 1 & 0 & 110 \\ 0 & 1 & 27 \\ \end {array} \right) \to \left ( \begin{array}{cc|c} 1 & -4 & 2 \\ 0 & 1 & 27 \\ \end {array} \right) \to \left ( \begin{array}{cc|c} 1 & -4 & 2 \\ -13 & 53 & 1 \\ \end {array} \right) \)
\( \underset{b}{0} \times \underset{m}{110} \times \underset{k}{(-13)} + \underset{a}{74} \times \underset{n}{27} \times \underset{t}{53} = \underset{c}{105,894} \equiv 1944 \mod \underset{mn}{2,970} \)
\([1944]_{2970}\)
c = 1944
print(c % 11)
print(c % 10)
print(c % 27)
8
4
0
4#
(i) Show that the polynomial \(x^4 + x^2 + 1\) has no integer roots, but that is has a root modulo \(3\), and factorize it over \(\mathbb{Z}_3\).