Chapter 4: Number Theory and Cryptography

Prove that if n is a positive integer such that the sum of the divisors of n is n+1, then n is prime.

This exercise outlines a proof of Fermat’s little theorem.

(a) Suppose thatis not divisible by the prime p. Show that no two of the integers $\mathbf{1}\mathbf{\cdot }\mathit{a}\mathbf{,}\mathbf{2}\mathbf{\cdot }\mathit{a}\mathbf{,}\mathbf{,}\mathbf{\dots }\mathbf{,}\mathbf{(}\mathit{p}\mathbf{-}\mathbf{1}\mathbf{)}\mathbf{\cdot }\mathit{a}$ are congruent modulo p .

(b) Conclude from part (a) that the product of $\mathbf{1}\mathbf{,}\mathbf{2}\mathbf{,}\mathbf{\dots }\mathbf{,}\mathit{p}\mathbf{-}\mathbf{1}$is congruent modulo to the product of $\mathbf{1}\mathbf{\cdot }\mathit{a}\mathbf{,}\mathbf{2}\mathbf{\cdot }\mathit{a}\mathbf{,}\mathbf{\dots }\mathbf{,}\mathbf{(}\mathit{p}\mathbf{-}\mathbf{1}\mathbf{)}\mathbf{\cdot }\mathit{a}$. Use this to show that $\mathbf{(}\mathit{p}\mathbf{-}\mathbf{1}\mathbf{)}\mathbf{!}\mathbf{=}{\mathit{a}}^{\mathit{p}\mathbf{-}\mathbf{1}}\mathbf{(}\mathit{p}\mathbf{-}\mathbf{1}\mathbf{)}\mathbf{!}\mathbf{(}\mathbf{mod}\mathit{p}\mathbf{)}$.

(c) Use Theorem 7 of section 4.3 to show that ${\mathit{a}}^{\mathit{p}\mathbf{-}\mathbf{1}}\mathbf{\equiv }\mathbf{1}\mathbf{(}\mathbf{mod}\mathit{p}\mathbf{)}$if$\mathit{p}\cancel{\mathbf{l}}\mathit{a}$from part (b) that if [Hint: Use lemma 3 of section 4.3 to show that does not divide$\mathbf{(}\mathbf{p}\mathbf{-}\mathbf{1}\mathbf{)}\mathbf{!}$ and then use theorem 7 of section 4.3. Alternatively, use Wilson’s theorem from exercise 18(b).]

(d) Use part (c) to show that${\mathbf{a}}^{\mathbf{p}}\mathbf{\equiv }\mathbf{a}\mathbf{(}\mathbf{mod}\mathbf{p}\mathbf{)}$ for all integers .

Give a procedure for converting from the octal expansion of an integer to its hexadecimal expansion using binary notation as an intermediate step.

The vigenere cipher is a block cipher, with a key that is a string of letters with numerical equivalents${\mathbf{k}}_{\mathbf{1}}\mathbf{,}{\mathbf{k}}_{\mathbf{2}}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}{\mathbf{k}}_{\mathbf{m}}$, where for${\mathbf{k}}_{\mathbf{i}}\in {\mathbf{Z}}_{\mathbf{26}}$ . Suppose that the numerical equivalents of the letters of a plain text block are${\mathbf{p}}_{\mathbf{1}}\mathbf{,}{\mathbf{p}}_{\mathbf{2}}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}{\mathbf{p}}_{\mathbf{m}}$ . The corresponding numerical cipher text block is $\mathbf{(}{\mathbf{P}}_{\mathbf{1}}\mathbf{+}{\mathbf{K}}_{\mathbf{1}}\mathbf{)}\mathbf{mod}\mathbf{26}\mathbf{(}{\mathbf{p}}_{\mathbf{2}}\mathbf{+}{\mathbf{k}}_{\mathbf{2}}\mathbf{)}\mathbf{mod}\mathbf{26}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{(}{\mathbf{p}}_{\mathbf{m}}\mathbf{+}{\mathbf{k}}_{\mathbf{m}}\mathbf{)}\mathbf{mod}\mathbf{26}$. Finally, we translate back to letters. For example, suppose that the key string is RED, with numerical equivalents1743.Then, the plain text ORANGE with numerical equivalents 14 1700 13 06 04is encrypted by first splitting it into twoblocks $\mathbf{14}\mathbf{}\mathbf{1700}\mathbf{}\mathbf{and}\mathbf{}\mathbf{13}\mathbf{}\mathbf{06}\mathbf{}\mathbf{04}$ . Then, in each block we shift the first letter by 17, the second by 4and the third by 3. We obtain $\mathbf{52103}\mathbf{}\mathbf{and}\mathbf{}\mathbf{04}\mathbf{}\mathbf{10}\mathbf{}\mathbf{07}$. The cipher text is $\mathbf{FVDEKH}$

19. The cipher text $\mathbf{OIKYWVHBX}$was produced by encrypting a plain text message using the vigenere cipher with key $\mathbf{HOT}$. What is plain text message?

Find a formula for the integer with smallest absolute value that is congruent to an integer a modulo m, where m is a positive integer.

The United States Postal Service (USPS) sells money orders identified by an \(11\)-digit number\({x_1}{x_2} \ldots {x_{11}}.\) The first ten digits identify the money order;\({x_{11}}\)is a check digit that satisfies\({x_{11}} = {x_1} + {x_2} + L + {x_{10}}\,mod\,9\) Determine whether each of these numbers is a valid USPS money order identification number.

\(\begin{aligned}{*{20}{l}}{a) 74051489623}\\{b) 88382013445}\\{c) 56152240784}\\{d) 66606631178}\end{aligned}\)

Explain how encryption and decryption are done in the RSA cryptosystem.

Show that every integer greater than 11 is the sum of two composite integers.

Does\(17\)divide each of these numbers?

a) \(68\)

b) \(84\)

c) \(357\)

d) \(1001\)

Convert the decimal expansion of each of these integers to a binaryexpansion.

1. \({\rm{231}}\)
2. \(4532\)
3. \(97644\)