Chapter 4: Number Theory and Cryptography

35. What integer does each of the following one’s complement representations of length five represent?

a) 11001 b) 01101 c) 10001 d) 11111

Does the check digit of an ISSN detect every error where two consecutive digits are accidentally interchanged? Justify your answer with either a proof or a counterexample.

Use Fermat’s little theorem to show that if $\mathit{p}$is prime and $\mathit{p}\mathit{\chi }\mathit{a}$, then role="math" localid="1668657209564" ${\mathit{a}}^{\mathbf{p}\mathbf{-}\mathbf{2}}$is an inverse of a modulo $\mathit{p}$

For which positive integers nis${\mathit{n}}^{\mathbf{4}}\mathbf{+}{\mathit{n}}^{\mathbf{4}}$ prime?

36. If m is a positive integer less than $2^{n-1}$, how is the one’s complement representation of −m obtained from the one’s complement of m, when bit strings of length n are used?

Use Exercise $35$to find an inverse of $5$modulo $41$

Show that if a and b are both positive integers, then $\left(2^a-1\right)mod\left(2^b-1\right)=2^{amodb}-1$

Show that the system of congruences $\mathbf{x}\mathbf{\equiv }\mathbf{2}\mathbf{}\mathbf{(}\mathbf{mod}\mathbf{}\mathbf{6}\mathbf{)}\mathbf{}\mathbf{and}\mathbf{}\mathbf{x}\mathbf{\equiv }\mathbf{3}\mathbf{}\mathbf{(}\mathbf{mod}\mathbf{}\mathbf{9}\mathbf{)}$has no solutions.

Use exercise 36 to show that if a and b are positive integers, then $\gcd \left(2^a-1,2^b-1\right)=2^{\gcd (a,b)}-1$

a) Show that$2^{340}=1(mod11)$by Fermat’s little theorem and nothing that.

b) Show that $2^{340}=1(mod31)$using the fact that $2^{340}={\left(2^5\right)}^{68}={32}^{68}$

c) Conclude from parts (a) and (b) thatlocalid="1668659996449" $2^{340}\equiv 1(mod341)$