Chapter 4: Number Theory and Cryptography

Show with the help of Fermat’s little theorem that if n is a positive integer then 42 divides${\mathbf{n}}^{\mathbf{7}}\mathbf{-}\mathbf{n}$

Prove that${\mathit{n}}^{\mathbf{12}}\mathbf{-}\mathbf{1}$is divisible by 35 for every integer

for which$\mathit{g}\mathit{c}\mathit{d}\mathbf{}\mathbf{(}\mathit{n}\mathbf{,}\mathbf{35}\mathbf{)}\mathbf{=}\mathbf{1}$

Answer Exercise 35if each expansion is a two's complement expansion of length five.

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

a)11001

b)01101

c)10001

d)11111

Show that if p is an odd prime, then every divisor of the Mersenne number ${\mathbf{2}}^{\mathbf{p}}\mathbf{-}\mathbf{1}$is of the form role="math" localid="1668665522353" $\mathbf{2}\mathit{k}\mathit{p}\mathbf{+}\mathbf{1}$where is a nonnegative integer [Hint: Use Fermat’s little theorem and Exercise 37 of Section4.3]

Use the extended Euclidean algorithm to express gcd(26,91) as a linear combination of 26 and 91.

Show that if Pand qare distinct prime numbers, then

${\mathit{p}}^{\mathbf{q}\mathbf{-}\mathbf{1}}\mathbf{+}{\mathit{q}}^{\mathbf{p}\mathbf{-}\mathbf{1}}\mathbf{\equiv }\mathbf{1}\mathbf{(}\mathbf{mod}\mathit{p}\mathit{q}\mathbf{)}$

$\mathbf{\text{Use Exercise}}\mathbf{41}\mathbf{\text{to determine whether}}{\mathit{M}}_{\mathbf{13}}\mathbf{=}{\mathbf{2}}^{\mathbf{13}}\mathbf{-}\mathbf{1}\mathbf{=}\mathbf{8191}\mathbf{\text{and}}{\mathit{M}}_{\mathbf{23}}\mathbf{=}{\mathbf{2}}^{\mathbf{23}}\mathbf{-}\mathbf{1}\mathbf{=}\mathbf{8}\mathbf{,}\mathbf{388}\mathbf{,}\mathbf{607}\mathbf{\text{are prime.}}$

Use the extended Euclidean algorithm to express as a linear combination of 245 and 356

Answer Exercise 36 for two's complement expansions.

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?

Determine whether each of these 13-digit numbers is a

valid.

a) $\mathbf{978}\mathbf{-}\mathbf{0}\mathbf{-}\mathbf{073}\mathbf{-}\mathbf{20679}\mathbf{-}\mathbf{1}$

b)$\mathbf{978}\mathbf{-}\mathbf{0}\mathbf{-}\mathbf{45424}\mathbf{-}\mathbf{521}\mathbf{-}\mathbf{1}$

c)$\mathbf{978}\mathbf{-}\mathbf{3}\mathbf{-}\mathbf{16}\mathbf{-}\mathbf{148410}\mathbf{-}\mathbf{0}$

d)$\mathbf{978}\mathbf{-}\mathbf{0}\mathbf{-}\mathbf{201}\mathbf{-}\mathbf{10179}\mathbf{-}\mathbf{9}$