Solutions

1.
Define the function f (i, j) = ij. From the Matrix submenu, choose Fill Matrix with 10 rows and 10 columns, and use the function f to generate a matrix. Then, reduce the matrix $\limfunc$mod11 to get the following: BITMAPSETProbSolvHint0.1807in0.2197in0inq1

$\displaystyle \fbox{$
\begin{array}{cccccccccc}
1 & 2 & 3 & 4 & 5 & 6 & 7 & 8...
...& 8 & 6 & 4 & 2 \\
10 & 9 & 8 & 7 & 6 & 5 & 4 & 3 & 2 & 1
\end{array}
$}
$

Select the matrix, from the Edit menu choose Insert Column(s), and add 1 column at position 1. You have now added a column on the left. Repeat this procedure using Insert Row(s), adding a row at position 1. Fill in the empty boxes with × and the integers 1 through 10 to generate the final multiplication table,

$\displaystyle \fbox{$
\begin{array}{ccccccccccc}
\times & 1 & 2 & 3 & 4 & 5 &...
... 6 & 4 & 2 \\
10 & 10 & 9 & 8 & 7 & 6 & 5 & 4 & 3 & 2 & 1
\end{array}
$}
$

From the table, 2⋅6 = 1 implies 2-1 = 6, and 3⋅4 = 1 implies -1 = 4. As a check, 2-1$\limfunc$mod11 = 6 and 3-1$\limfunc$mod11 = 4.

2.
The solution is given by x = (8 - 4)/5$\limfunc$mod13 =  6. As a check, 6⋅5 + 4$\limfunc$mod13 =  8.BITMAPSETProbSolvHint0.1807in0.2197in0inq2

3.
The problem requires the solution to the system
x 3  $\displaystyle \left(\vphantom{ \limfunc{mod}5}\right.$$\displaystyle \limfunc$mod5$\displaystyle \left.\vphantom{ \limfunc{mod}5}\right)$  
x 5  $\displaystyle \left(\vphantom{ \limfunc{mod}7}\right.$$\displaystyle \limfunc$mod7$\displaystyle \left.\vphantom{ \limfunc{mod}7}\right)$  

of congruences. The system is equivalent to the equation x = 3 + 5a = 5 + 7b, or + 5a≡5  $\left(\vphantom{ \limfunc{mod}7}\right.$$\limfunc$mod7$\left.\vphantom{ \limfunc{mod}7}\right)$, which has a solution a = (5 - 3)/5$\limfunc$mod7 = 6, which means x = 3 + 5a = 33 jelly beans. Other possible solutions are x = 33 + 35n, where n is any positive integer.BITMAPSETProbSolvHint0.1807in0.2197in0inq3

4.
Define the function $\limfunc$nextp as indicated in this chapter. Then $\limfunc$nextp(1099) produces a number with lots of zeroes that ends in 289. The prime p can be written as p = 1099 + 289.BITMAPSETProbSolvHint0.1807in0.2197in0inq4

5.
Note that 2p-1$\limfunc$modp = 1 and 2(p-1)/2$\limfunc$modp = 1, whereas 2(p-1)/4$\limfunc$modp produces another number with lots of zeroes that ends in 288. More precisely, (p-1)/4≡ -1$\limfunc$modp. This congruence illustrates the fact that, if p is a prime, then x2≡1  $\left(\vphantom{ \limfunc{mod}p}\right.$$\limfunc$modp$\left.\vphantom{ \limfunc{mod}p}\right)$ has only two solutions, x≡1  $\left(\vphantom{ \limfunc{mod}p}\right.$$\limfunc$modp$\left.\vphantom{ \limfunc{mod}p}\right)$ and x≡ -1  $\left(\vphantom{ \limfunc{mod}p}\right.$$\limfunc$modp$\left.\vphantom{ \limfunc{mod}p}\right)$.BITMAPSETProbSolvHint0.1807in0.2197in0inq5

6.
We have $\left[\vphantom{
\begin{array}{ccc}
1 & 1 & 1 \\
1 & 2 & 4 \\
1 & 4 & 9
\end{array}
}\right.$$\begin{array}{ccc}
1 & 1 & 1 \\
1 & 2 & 4 \\
1 & 4 & 9
\end{array}$$\left.\vphantom{
\begin{array}{ccc}
1 & 1 & 1 \\
1 & 2 & 4 \\
1 & 4 & 9
\end{array}
}\right]^{{-1}}_{}$$\limfunc$mod26 = $\left[\vphantom{
\begin{array}{ccc}
24 & 5 & 24 \\
5 & 18 & 3 \\
24 & 3 & 25
\end{array}
}\right.$$\begin{array}{ccc}
24 & 5 & 24 \\
5 & 18 & 3 \\
24 & 3 & 25
\end{array}$$\left.\vphantom{
\begin{array}{ccc}
24 & 5 & 24 \\
5 & 18 & 3 \\
24 & 3 & 25
\end{array}
}\right]$. The ciphertext F K B H R T M T U has a numerical equivalent of $\left[\vphantom{ 5,10,1,7,17,19,12,19,20}\right.$5, 10, 1, 7, 17, 19, 12, 19, 20$\left.\vphantom{ 5,10,1,7,17,19,12,19,20}\right]$. Picking three at a time, we get

$\displaystyle \left[\vphantom{
\begin{array}{ccc}
24 & 5 & 24 \\
5 & 18 & 3 \\
24 & 3 & 25
\end{array}
}\right.$$\displaystyle \begin{array}{ccc}
24 & 5 & 24 \\
5 & 18 & 3 \\
24 & 3 & 25
\end{array}$$\displaystyle \left.\vphantom{
\begin{array}{ccc}
24 & 5 & 24 \\
5 & 18 & 3 \\
24 & 3 & 25
\end{array}
}\right]$$\displaystyle \left[\vphantom{
\begin{array}{ccc}
5 & 7 & 12 \\
10 & 17 & 19 \\
1 & 19 & 20
\end{array}
}\right.$$\displaystyle \begin{array}{ccc}
5 & 7 & 12 \\
10 & 17 & 19 \\
1 & 19 & 20
\end{array}$$\displaystyle \left.\vphantom{
\begin{array}{ccc}
5 & 7 & 12 \\
10 & 17 & 19 \\
1 & 19 & 20
\end{array}
}\right]$$\displaystyle \limfunc$mod26 = $\displaystyle \left[\vphantom{
\begin{array}{ccc}
12 & 7 & 5 \\
0 & 8 & 20 \\
19 & 18 & 13
\end{array}
}\right.$$\displaystyle \begin{array}{ccc}
12 & 7 & 5 \\
0 & 8 & 20 \\
19 & 18 & 13
\end{array}$$\displaystyle \left.\vphantom{
\begin{array}{ccc}
12 & 7 & 5 \\
0 & 8 & 20 \\
19 & 18 & 13
\end{array}
}\right]$

The vector $\left[\vphantom{ 12,0,19,7,8,18,5,20,13}\right.$12, 0, 19, 7, 8, 18, 5, 20, 13$\left.\vphantom{ 12,0,19,7,8,18,5,20,13}\right]$ corresponds to the plaintext M A T H I S F U N, or MATH IS FUN.BITMAPSETProbSolvHint0.1807in0.2197in0inq6

7.
Defining g(x) = x3 + x + 1, we see that g(1)$\limfunc$mod3 = 0, and hence g(x) is not irreducible (since it has a root in GF3). However, if f (x) = x3 + 2x + 1, then f (0)$\limfunc$mod3 = 1, f (1)$\limfunc$mod3 = 1, and f (2)$\limfunc$mod3 = 1, and hence f (x) is irreducible. (If f (x) were reducible, it would have a linear factor, and hence a root.) An element of GF27 can be thought of as a polynomial of degree less than 3 with coefficients in GF3. Given the field elements 2x2 + x + 2 and x + 1, the product is $\left(\vphantom{ \left( 2x^{2}+x+2\right) \left( 2x+1\right)
\limfunc{mod}\;x^{3}+2x+1}\right.$$\left(\vphantom{ 2x^{2}+x+2}\right.$2x2 + x + 2$\left.\vphantom{ 2x^{2}+x+2}\right)$$\left(\vphantom{ 2x+1}\right.$2x + 1$\left.\vphantom{ 2x+1}\right)$$\limfunc$mod  x3 + 2x + 1$\left.\vphantom{ \left( 2x^{2}+x+2\right) \left( 2x+1\right)
\limfunc{mod}\;x^{3}+2x+1}\right)$$\limfunc$mod3 = x2 + 1, and the sum is given by $\left(\vphantom{ 2x^{2}+x+2}\right.$2x2 + x + 2$\left.\vphantom{ 2x^{2}+x+2}\right)$ + $\left(\vphantom{ 2x+1}\right.$2x + 1$\left.\vphantom{ 2x+1}\right)$$\limfunc$mod3 = 2x2.BITMAPSETProbSolvHint0.1807in0.2197in0inq7

8.
The objective function is 2.3h + 3b. The constraints are 4h + 5b≤8000, 75h + 100b≤150000, b≥ 0, and h≥ 0. Apply Maximize from the Simplex submenu to the system

2.3h + 3b
5h + 4b≤8000
75h + 100b≤150000
b≥ 0
h≥ 0

to get the result: Maximum is 4550 at h = 1000, b = 750. BITMAPSETProbSolvHint0.1807in0.2197in0inq8



Subsections