# Review Problems for Test 3

Math 393

These problems are provided to help you study. The presence of a problem on this handout does not imply that there will be a similar problem on the test. And the absence of a topic does not imply that it won't appear on the test.

1. Find the decoding transformation for the affine transformation cipher

2. Find the decoding transformation for the digraphic cipher

3. Calvin Butterball constructs the following digraphic cipher:

Show that this is a bad idea by finding two different plaintext blocks that give the same ciphertext block.

4. Find the decoding transformation for the exponential cipher

5. Suppose that is a product of two primes p and q, and that . Without factoring n directly, find p and q.

6. (a) Use an RSA cipher with and exponent 27 to encipher the word OMELET.

(b) Find the decoding transformation for the cipher in part (a).

7. Find a solution to the following quadratic congruence.

(Note that .)

8. Solve . [Note: .]

9. Find the quadratic residues mod 17.

10. Find the quadratic residues mod 18.

11. Compute the following Legendre symbols:

(a) .

(b) .

(c) .

(d) , if is prime.

(e) Compute .

12. Determine whether has solutions. (Note: 1301 is prime.)

13. State the Law of Quadratic Reciprocity in terms of congruences, and in terms of Legendre symbols.

14. Show that if p is an odd prime and 2, 3, and 6 are distinct mod p, then at least one of 2, 3, or 6 is a quadratic residue mod p.

15. Use Gauss's lemma to determine whether has any solutions.

16. Compute the following Jacobi symbols.

(a) .

(b) .

17. Let p be an odd prime. Prove that

18. Convert to base 10.

19. Convert 1808 to base 7.

20. Express 0.3 in base-7.

21. Express as a decimal fraction in lowest terms.

22. Let b be a positive integer greater than 3. Express as a rational function of b.

23. Let b be a positive integer greater than 3. Find the base b expansion of .

24. Find the finite continued fraction expansion for .

25. Find the successive convergents and the exact value of the finite continued fraction .

26. Suppose x is a positive integer. Find the exact value of

27. Use continued fractions to find an integer linear combination of 501 and 113 which is equal to 1.

# Solutions to the Review Problems for Test 3

1. Find the decoding transformation for the affine transformation cipher

Therefore,

2. Find the decoding transformation for the digraphic cipher

Find the inverse of the matrix:

Use the Euclidean algorithm to compute :

Thus,

Therefore, , and the inverse matrix is

The decoding transformation is

3. Calvin Butterball constructs the following digraphic cipher:

Show that this is a bad idea by finding two different plaintext blocks that give the same ciphertext block.

The problem, of course, is that

I want , , , , such that , but

Moving all the terms to the left side and factoring, I have

I see that what I need is a nontrivial (i.e. nonzero) solution to the homogeneous system

To do this, row reduce. To find out how to "divide" the first row by 7, use the Extended Euclidean Algorithm:

Thus,

I can't go any further, because 13 isn't invertible mod 26.

These equations say

I want a nonzero solution. So take to satisfy the second equation. (Any even number will work for y.) Plugging this into the first equation, I get

Finally, recall that represents . So to get two different plaintexts that give the same ciphertext, set to anything --- say --- and add to get .

You can check that

Try setting (say), so . You can verify for yourself that this choice of and will work as well.

4. Find the decoding transformation for the exponential cipher

I need to find .

, so the decoding transformation is

Note: The inverse must be converted to a positive number before being used as the exponent in the decoding transformation. For example, if the original exponent had been 19, then

The decoding transformation would then be .

5. Suppose that is a product of two primes p and q, and that . Without factoring n directly, find p and q.

I have

Thus,

Therefore,

So

Hence, . The primes are 149 and 541.

6. (a) Use an RSA cipher with and exponent 27 to encipher the word OMELET.

(b) Find the decoding transformation for the cipher in part (a).

(a) Note that , and .

since , I use blocks of 2 letters.

Translate OMELET to 1412 0411 0419. To encipher the first block, for example, I compute

Proceeding in the same way, I obtain the ciphertext 1677 0288 1139.

(b) I need to find d such that . Use the Euclidean algorithm:

This means that

Since , I can take . The decoding transformation is

7. Find a solution to the following quadratic congruence.

(Note that .)

First, consider the congruence mod 23:

Clearly, is a solution.

I'll try to find a solution to the original congruence:

Note that . Dividing the congruence by 92, I must divide the modulus by :

Then a solution is given by

Note that also works.

8. Solve .

, so this is equivalent to solving

becomes , which has solutions .

becomes .

(I obviously don't need to check , and the squares from 16 to 30 repeat those from 1 to 15, backwards.)

The solutions are .

Now take cases. If and , then

I need to find . Use the Extended Euclidean Algorithm:

Thus, . So

If and , then

The other solutions are and .

All together, the solutions are .

9. Find the quadratic residues mod 17.

The quadratic residues mod 17 are 1, 2, 4, 8, 9, 13, 15, and 16.

10. Find the quadratic residues mod 18.

Of the squares mod 18, only 1, 7, and 13 are relatively prime to 18. So the quadratic residues mod 18 are 1, 7, and 13.

11. Compute the following Legendre symbols:

(a) .

(b) .

(c) .

(d) , if is prime.

(e) .

(a) Since and , reciprocity gives

Now if p is an odd prime,

So

Hence, .

(b)

As in (a),

Thus, .

(c) 569 is prime.

, so

, because 4 is a perfect square.

, so

Therefore,

(d) Since , Quadratic Reciprocity gives

(e)

To compute , I used the formula . You could also compute the last symbol using Euler's Theorem.

12. Determine whether has solutions. (Note: 1301 is prime.)

Hence, has solutions.

13. State the Law of Quadratic Reciprocity in terms of congruences, and in terms of Legendre symbols.

Let p and q be distinct odd primes.

In terms of congruences, reciprocity says: Consider the congruences

If either p or q has the form for , then both congruences have solutions or both do not have solutions.

If both and for , then one congruence is solvable and the other is not.

In terms of Legendre symbols, reciprocity says:

An equivalent statement in terms of symbols is this: If either p or q has the form for , then .

If both and for , then .

14. Show that if p is an odd prime and 2, 3, and 6 are distinct mod p, then at least one of 2, 3, or 6 is a quadratic residue mod p.

I have

Suppose 2, 3, and 6 are quadratic nonresidues mod p. Then all three of the symbols , , and are -1, and the equation above says " ", a contradiction. Hence, at least one of the three is a quadratic residue mod p.

15. Use Gauss's lemma to determine whether has any solutions.

Gauss's lemma applies, since . , so I compute the first 8 multiples of 15 mod 17:

Now , and 4 of these residues are greater than 8.5. By Gauss's lemma,

Therefore, has solutions.

16. Compute the following Jacobi symbols.

(a) .

(b) .

(a)

(b) By direct computation 3 isn't a square mod 7, so

17. Let p be an odd prime. Prove that

Note for all four cases that

If , then

Hence, .

If , then

Hence, .

If , then

Hence, .

If , then

Hence, .

18. Convert to base 10.

Note that

Thus, I need to plug into the polynomial . I can do this, for instance, using synthetic division (Horner's method):

Hence, .

19. Convert 1808 to base 7.

I can do this by successive division by 7:

To see why this works, suppose that

Rewrite the right side using Horner's method:

is the remainder when 1808 is divided by 7. The quotient is ; if I divide this quotient by 7, the remainder is . And so on.

Thus, .

20. Express 0.3 in base-7.

For example, in the first row I multiplied 0.3 by the base 7 to get 2.1. I took the integer part of 2.1, which is 2, and put it in the first spot in the second row. Then , and that goes into the second spot in the second row. Then I just repeat the process: , the integer part of 0.7 is 0, subtracting gives , and so on. I keep going until the numbers repeat, at which point I have the expansion.

You can see why this gives the base b expansion of a number x by writing

The digits I want are , , and so on. Multiplying x by b gives

The integer part is , and the fractional part is

Then I get by multiplying this by b, and so on.

Thus, .

21. Express as a decimal fraction in lowest terms.

Let . Since the repeating part has two digits, I multiply by to get

Here's an explanation for the subtraction. The repeating 42's on the far right cancel. In the place to the right of the point, I'm doing 2 minus 5. As usual, I have to borrow 1 from the 4 to the left, which is where the "53" comes from. After borrowing, in the place to the right of the point, I'm doing . This is in decimal, so the digit to the right of the point is 3.

I still have to convert to decimal before I solve for x:

So

22. Let b be a positive integer greater than 3. Express as a rational function of b.

Write the expression as an infinite series and use the formula for the sum of a geometric series:

23. Let b be a positive integer greater than 3. Find the base b expansion of .

The idea in this problem is to try to expand the expression in a power series in . One way to do this is to make use of the geometric series

If for some k, I'll get a power series in . So I do some algebra to get expressions of the right form.

24. Find the finite continued fraction expansion for .

Do the Euclidean algorithm:

25. Find the successive convergents and the exact value of the finite continued fraction .

26. Suppose x is a positive integer. Find the exact value of

The expression is the finite continued fraction .

27. Use continued fractions to find an integer linear combination of 501 and 113 which is equal to 1.

First, find the continued fraction expansion of :

Next, find the convergents:

Finally, take the "cross product" of the p's and q's in the last two rows:

To be honest, one must be inconsistent. - H. G. Wells

Contact information