1.4 1.4 #

Exercises from Humphreys, J. F. & M. Y. Prest. (2008). Numbers, Groups, and Codes. 2nd Ed. Cambridge University Press.

Programming Environment #

import numpy as np

KaTeX \(\renewcommand{\c}[1]{\textcolor{#1}}\)

1 #

Determine which of the following are true (a calculator will be useful for the larger numbers).

\( \begin{aligned} 8 & \not\equiv 48 \mod 14 &&\iff 14 \nmid 48 - 8 = 40 &&\iff 2 \times 7 \nmid 2^3 \times 5 \\ -8 & \equiv 48 \mod 14 &&\iff 14 \mid 48 + 8 = 56 &&\iff 2 \times 7 \mid 2^3 \times 7 \\ 10 & \not\equiv 0 \mod 100 &&\iff 100 \nmid 10 - 0 = 10 &&\iff 2^2 \times 5^2 \nmid 2 \times 5 \\ 7754 & \equiv 357482 \mod 3643 &&\iff 3643 \mid 357482 - 7754 = 349728 &&\iff 3643 \mid 2^5 \times 3 \times 3643 \\ 16023 & \equiv 1325227 \mod 25177 &&\iff 25177 \mid 1325227 - 16023 = 1309204 &&\iff 17 \times 1481 \mid 2^2 \times 13 \times 17 \times 1481 \\ 4015 & \not\equiv 33303 \mod 1295 &&\iff 1295 \nmid 33303 - 4015 = 29288 &&\iff 5 \times 7 \times 37 \nmid 2^3 \times 7 \times 523\\ \end{aligned} \)

3 #

Find the following inverses, if they exist.

\( \begin{aligned} 7r &\equiv 1 \mod 11 &&\iff 7r - 1 = 11s &&\iff r = \frac{ 11(s = 5) + 1}{ 7} = 8 \\ 10r &\equiv 1 \mod 26 &&gcd(10, 26) = 2\\ 11r &\equiv 1 \mod 31 &&\iff 11r - 1 = 31s &&\iff r = \frac{ 31(s = 6) + 1}{11} = 17 \\ 23r &\equiv 1 \mod 31 &&\iff 23r - 1 = 31s &&\iff r = \frac{ 31(s = 20) + 1}{23} = 27 \\ 91r &\equiv 1 \mod 237 &&\iff 91r - 1 = 237s &&\iff r = \frac{237(s = 43) + 1}{91} = 112 \\ \end{aligned} \)

print(np.gcd( 7,  11))
print(np.gcd(10,  26))
print(np.gcd(11,  31))
print(np.gcd(23,  31))
print(np.gcd(91, 237))

6 - The only elements of \(\mathbb{Z}_p^*\) that are self-inverse are \(1\) and \(p - 1\)#

Let \(p\) be a prime number. Show that the equation \(x^2 = [1]_p\) has just two solutions in \(\mathbb{Z}_p\).

\([x^2]_p = [1]_p \iff x^2 \equiv 1 \mod p \iff p \mid x^2 - 1 = (x + 1)(x - 1)\)

\(\text{Euclid's Lemma:} \,\, p \mid (x + 1)(x - 1) \implies (p \mid x + 1) \lor (p \mid x - 1)\)

\( \begin{aligned} p \mid x + 1 &\iff x \equiv -1 \mod p &&\iff [x]_p = [-1]_p = [p - 1]_p \\ p \mid x - 1 &\iff x \equiv 1 \mod p &&\iff [x]_p = [ 1]_p \\ \end{aligned} \)

7 - Wilson’s Theorem #

Let \(p\) be a prime number. Show that \((p - 1)! \equiv -1 \mod p\).

Since \(p\) is prime, every positive integer less than \(p\) is relatively prime to \(p\). Therefore, every element of \(\mathbb{Z}_p^*\) has an inverse in \(\mathbb{Z}_p^*\).

\(\mathbb{Z}_p^* = \{1, 2, \dots, p - 2, p - 1\}\)

\((p - 1)! = 1 \times 2 \times \dots \times p - 2 \times p - 1\)

\([y]_p := [x]_p^{-1}\)

\([x]_p [y]_p = [1]_p \iff [xy]_p = [1]_p \iff xy \equiv 1 \mod p\)

There are only two elements that are self-inverse; namely, \([1]_p\) and \([-1]_p = [p - 1]_p\)

\(|\mathbb{Z}_p^*| = p - 1\)

\(|\mathbb{Z}_p^* - \{ 1, p - 1 \}| = p - 3\)

The remaining elements of \(\mathbb{Z}_p^*\) can be separated into \(\frac{p - 3}{2}\) pairs of the form \(([x]_p, [x]_p^{-1})\) where \([x]_p [x]_p^{-1} = [1]_p\).

\([(p - 1)!]_p = [1 \times 2 \times \dots \times p - 2 \times p - 1]_p = [1 \times \underbrace{1 \times \dots \times 1}_{\frac{p - 3}{2}} \times p - 1]_p = [p - 1]_p = [-1]_p\)

8 #

Choose a value of \(n\) and count the number of elements in \(\mathbb{Z}_n^*\). Try this with various values of \(n\). Can you discover any rules governing the relation between \(n\) and the number of elements in \(\mathbb{Z}_n^*\)?

9 - Casting out nines #

The observation that \(10 \equiv 1 \mod 9\) is the basis for the procedure of ‘casting out nines’. The method is as follows. Given an integer \(X\) written in base \(10\) (as is usual), compute the sum of the digits of \(X\): call the result the digit sum of \(X\). If the digit sum is greater than \(9\), we form the digit sum again. Continue in this way to obtain the iterated digit sum which is at most \(9\). (Thus \(5,734\) has digit sum \(19\) which has digit sum \(10\) which has digit sum \(1\), so the iterated digit sum of \(5,734\) is \(1\).)

\( \begin{alignedat}{5} \boxed{19} &= \c{cyan}{5} + 7 + 3 + \c{cyan}{4} &\quad 10 &= 7 + 3 &\quad 10 &= \boxed{19} - \c{cyan}{9} \\ 10 &= 1 + \c{cyan}{9} \\ 1 &= 1 + 0 & 1 &= 1 + 0 & 1 &= \boxed{19} - \c{cyan}{9} \times 2 \\ \end{alignedat} \)

5_734 % 9

Now suppose that we have a calculation which we want to check by hand: say, for example, someone claims that \(873,985 \times 79,041 = 69,069,967,565\). Compute the iterated digit sums of \(873,985\) and \(79,041\) (these are \(4\) and \(3\), respectively), multiply these together (to get \(12\)), and form the iterated digit sum of the product (which is \(3\)). Then the result should equal the iterated digit sum of \(69,069,967,565\) (which is \(5\)). Since it does not, the ‘equality’ is incorrect. If the results had been equal then all we could say would be that no error was detected.

\( \begin{alignedat}{5} \boxed{40} &= \c{cyan}{8} + \c{cyan}{7} + \c{cyan}{3} + \c{cyan}{9} + 8 + 5 &\quad 13 &= 8 + 5 &\quad 13 &= \boxed{40} - \c{cyan}{9} \times 3 \\ \c{red}{4} &= 4 + 0 & \c{red}{4} &= 1 + 3 &\quad 4 &= \boxed{40} - \c{cyan}{9} \times 4 \\ \boxed{21} &= 7 + \c{cyan}{9} + 0 + 4 + 1 & 12 &= 7 + 0 + 4 + 1 &\quad 12 &= \boxed{21} - \c{cyan}{9} \\ \c{red}{3} &= 2 + 1 & \c{red}{3} &= 1 + 2 &\quad 3 &= \boxed{21} - \c{cyan}{9} \times 2 \\ 12 &= \c{red}{4} \times \c{red}{3} \\ \c{orange}{3} &= 1 + 2 \\ \boxed{68} &= \c{cyan}{6} + \c{cyan}{9} + 0 + \c{cyan}{6} + \c{cyan}{9} + \c{cyan}{9} + \c{cyan}{6} + 7 + 5 + 6 + 5 & 23 &= 7 + 5 + 6 + 5 &\quad 23 &= \boxed{68} - \c{cyan}{9} \times 5 \\ 14 &= 6 + 8 & & &\quad 14 &= \boxed{68} - \c{cyan}{9} \times 6 \\ \c{yellow}{5} &= 1 + 4 & \c{yellow}{5} &= 2 + 3 &\quad 5 &= \boxed{68} - \c{cyan}{9} \times 7\\ \end{alignedat} \)

\(\c{orange}{3} \ne \c{yellow}{5} \therefore 873,985 \times 79,041 \ne 69,069,967,565\)

a =        873_985
b =         79_041
c = 69_069_967_565

print(a     % 9)
print(  b   % 9)
print(a*b   % 9)
print(    c % 9)
print(a*b)
print(c)

4
3
3
5
69080648385
69069967565

(i) Using the method of casting out nines what can you say about the following computations?

\( \begin{aligned} 56,563 \times 9,961 &\overset{?}{=} 563,454,043 \\ 1,234 \times 5,678 \times 901 &\overset{?}{=} 6,213,993,452 \\ 333 \times 666 \times 999 &\overset{?}{=} 221,556,222 \\ \end{aligned} \)

\( \begin{aligned} 56,563 \times 9,961 &\ne 563,454,043 \\ 1,234 \times 5,678 \times 901 &\ne 6,213,993,452 \\ 333 \times 666 \times 999 &= 221,556,222 \\ \end{aligned} \)

\( \begin{alignedat}{3} 25 &= 5 + 6 + 5 + 6 + 3 \\ \c{red}{7} &= 2 + 5 \\ 25 &= \c{cyan}{9} + \c{cyan}{9} + 6 + 1 \\ \c{red}{7} &= 2 + 5 &\quad \c{red}{7} &= 6 + 1 \\ 49 &= \c{red}{7} \times \c{red}{7} \\ 13 &= 4 + \c{cyan}{9} \\ \c{orange}{4} &= 1 + 3 & \c{orange}{4} &= 4 \\ 34 &= \c{cyan}{5} + \c{cyan}{6} + \c{cyan}{3} + \c{cyan}{4} + \c{cyan}{5} + \c{cyan}{4} + 0 + 4 + 3 \\ \c{yellow}{7} &= 3 + 4 & \c{yellow}{7} &= 4 + 3 \\ \end{alignedat} \)

\(\c{orange}{4} \ne \c{yellow}{7} \therefore 56,563 \times 9,961 \ne 563,454,043\)

a =      56_563
b =       9_961
c = 563_454_043

print(a     % 9)
print(  b   % 9)
print(a*b   % 9)
print(    c % 9)
print(a*b)
print(c)

\( \begin{alignedat}{3} 10 &= 1 + \c{cyan}{2} + \c{cyan}{3} + \c{cyan}{4} \\ \c{red}{1} &= 1 + 0 &\quad \c{red}{1} &= 1 \\ 26 &= \c{cyan}{5} + \c{cyan}{6} + \c{cyan}{7} + 8 \\ \c{red}{8} &= 2 + 6 & \c{red}{8} &= 8 \\ 10 &= \c{cyan}{9} + 0 + 1 \\ \c{red}{1} &= 1 + 0 & \c{red}{1} &= 1 \\ \c{orange}{8} &= \c{red}{1} \times \c{red}{8} \times \c{red}{1} \\ 44 &= \c{cyan}{6} + \c{cyan}{2} + \c{cyan}{1} + \c{cyan}{3} + \c{cyan}{9} + \c{cyan}{9} + 3 + \c{cyan}{4} + 5 + \c{cyan}{2} \\ \c{yellow}{8} &= 4 + 4 & \c{yellow}{8} &= 3 + 5 \\ \end{alignedat} \)

\(\c{orange}{8} = \c{yellow}{8} \therefore \,\, \text{no error detected}\)

a =         1_234
b =         5_678
d =           901
c = 6_213_993_452

print(a       % 9)
print(  b     % 9)
print(    d   % 9)
print(a*b*d   % 9)
print(      c % 9)
print(a*b*d)
print(c)

\( \begin{alignedat}{3} \c{red}{9} &= \c{cyan}{3} + \c{cyan}{3} + \c{cyan}{3} \\ 18 &= \c{cyan}{6} + \c{cyan}{6} + \c{cyan}{6} \\ \c{red}{9} &= 1 + 8 \\ 27 &= \c{cyan}{9} + \c{cyan}{9} + \c{cyan}{9} \\ \c{red}{9} &= 2 + 7 \\ 729 &= \c{red}{9} \times \c{red}{9} \times \c{red}{9} \\ 18 &= \c{cyan}{7} + \c{cyan}{2} + \c{cyan}{9} \\ \c{orange}{9} &= 1 + 8 \\ 27 &= \c{cyan}{2} + \c{cyan}{2} + \c{cyan}{1} + \c{cyan}{5} + \c{cyan}{5} + \c{cyan}{6} + \c{cyan}{2} + \c{cyan}{2} + \c{cyan}{2} \\ \c{yellow}{9} &= 2 + 7 \\ \end{alignedat} \)

\(\c{orange}{9} = \c{yellow}{9} \therefore \,\, \text{no error detected}\)

a =         333
b =         666
d =         999
c = 221_556_222

print(a       % 9)
print(  b     % 9)
print(    d   % 9)
print(a*b*d   % 9)
print(      c % 9)
print(a*b*d)
print(c)

(ii) The following equation is false but you are told that only the underlined digit is in error. What is the correct value for that digit?

\(674,532 \times 9,764 = 6,586,1 \underline 40,448\)

\( \begin{alignedat}{3} 27 &= \c{cyan}{6} + \c{cyan}{7} + \c{cyan}{4} + \c{cyan}{5} + \c{cyan}{3} + \c{cyan}{2} \\ \c{red}{9} &= 2 + 7 \\ 26 &= \c{cyan}{9} + 7 + 6 + 4 &\quad 17 &= 7 + 6 + 4 \\ \c{red}{8} &= 2 + 6 & \c{red}{8} &= 1 + 7 \\ 72 &= \c{red}{9} \times \c{red}{8} \\ \c{orange}{9} &= \c{cyan}{7} + \c{cyan}{2} \\ 46 &= 6 + 5 + \c{cyan}{8} + \c{cyan}{6} + \c{cyan}{1} + \c{cyan}{4} + 0 + \c{cyan}{4} + \c{cyan}{4} + 8 & 19 &= 6 + 5 + 8 \\ 10 &= 4 + 6 & 10 &= 1 + 9 \\ \c{yellow}{1} &= 1 + 0 & \c{yellow}{1} &= 1 + 0 \\ \end{alignedat} \)

\(\c{orange}{9} \ne \c{yellow}{1} \therefore 674,532 \times 9,764 \ne 6,586,1 \underline 40,448\)

\( \begin{alignedat}{3} 45 &= \c{cyan}{6} + \c{cyan}{5} + \c{cyan}{8} + \c{cyan}{6} + \c{cyan}{1} + \c{cyan}{(4 - 1)} + 0 + \c{cyan}{4} + \c{cyan}{4} + \c{cyan}{8} \\ \c{yellow}{9} &= 4 + 5 \\ \end{alignedat} \)

\(\c{orange}{9} = \c{yellow}{9} \therefore \,\, \text{no error detected}\)

a =       674_532
b =         9_764
c = 6_586_140_448

print(a     % 9)
print(  b   % 9)
print(a*b   % 9)
print(    c % 9)
print(a*b)
print(c)

(iii) Justify the method of casting out nines.

1.4

Contents

1.4 #

Table of Contents #

Programming Environment #

1 #

3 #

6 - The only elements of \(\mathbb{Z}_p^*\) that are self-inverse are \(1\) and \(p - 1\)#

7 - Wilson’s Theorem #

8 #

9 - Casting out nines #