Chapter 4: Number Theory and Cryptography

37. How is the one’s complement representation of the sum of two integers obtained from the one’s complement representations of these integers?

Find all solutions of the system of congruences $\mathit{x}\mathbf{\equiv }\mathbf{4}\mathbf{\left(}\mathit{m}\mathit{o}\mathit{d}\mathbf{6}\mathbf{\right)}$and$\mathit{x}\mathbf{\equiv }\mathbf{13}\mathbf{\left(}\mathit{m}\mathit{o}\mathit{d}\mathbf{15}\mathbf{\right)}$.

a) use Fermat’s little theorem to compute$3^{302}mod5$and$3^{302}mod7,3^{302}mod11$.

b) Use your results from part (a) and the Chinese remainder theorem to find $3^{302}mod385$. (Note that$385=\mathrm{5.7.11}$)

Use exercise 37 to show that the integers $2^{35}-1,2^{34}-1,2^{33}-1,2^{31}-1,2^{29}-1$and$2^{23}-1$ are pair wise relatively prime.

38. How is the one’s complement representation of the difference of two integers obtained from the one’s complement representations of these integers?

a) Show that the system of congruences $\mathit{x}\mathbf{\equiv }{\mathit{a}}_{\mathbf{1}}\mathbf{(}\mathit{m}\mathit{o}\mathit{d}\mathbf{}{\mathit{m}}_{\mathbf{1}}\mathbf{)}$

and $\mathit{x}\mathbf{\equiv }{\mathit{a}}_{\mathbf{2}}\mathbf{(}\mathit{m}\mathit{o}\mathit{d}\mathbf{}{\mathit{m}}_2\mathbf{)}$, where ${\mathit{a}}_{\mathbf{1}}\mathbf{,}{\mathit{a}}_{\mathbf{2}}\mathbf{,}{\mathit{m}}_{\mathbf{1}}$,and ${\mathit{m}}_{\mathbf{2}}$are integers with ${\mathit{m}}_{\mathbf{1}}\mathbf{>}\mathbf{0}$ and${\mathit{m}}_{\mathbf{2}}\mathbf{>}\mathbf{0}$ , has a solution if and only if $\mathit{g}\mathit{c}\mathit{d}\left(m_1,m_2\right)\mathbf{|}{\mathit{a}}_{\mathbf{1}}\mathbf{-}{\mathit{a}}_{\mathbf{2}}$

b) Show that if the system in part (a) has a solution, then it is unique modulo ${\mathit{m}}_{\mathbf{1}}\mathbf{,}{\mathit{m}}_{\mathbf{2}}$

39. Show that the integer m with one’s complement representation $\left(a_{n-1}{a}_{n-2}\dots a_1{a}_0\right)$can be found using the equation$m=-a_{n-1}\left(2^{n-1}-1\right)+a_{n-2}{2}^{n-2}+\dots .+a_1\cdot 2+a_0$

Using the method followed in Example 17, express the greatest common divisor of each of these pairs of integers as a linear combination of these integers.

a) Use Fermat’s little theorem to compute ${\mathbf{5}}^{\mathbf{2003}}\mathbf{mod}\mathbf{7}$and ${\mathbf{5}}^{\mathbf{2003}}\mathbf{mod}\mathbf{11}\mathbf{\text{and}}{\mathbf{5}}^{\mathbf{2003}}\mathbf{mod}\mathbf{13}$

b) Use your results from part (a) and the Chinese remainder theorem to find ${\mathbf{5}}^{\mathbf{2003}}\mathbf{mod}\mathbf{1001}$. (Note that$\mathbf{}\mathbf{1001}\mathbf{=}\mathbf{7.11.13}$)

Prove that 30 divides ${\mathit{n}}^{\mathbf{9}}\mathbf{-}\mathit{n}$for every nonnegative Integer n.