Exam 4: A: Number Theory and Cryptography

Prove or disprove: For all integers $a , b , c \text {, if } a \mid c \text { and } b \mid c \text {, then } ( a + b ) \mid c \text {. }$

determine whether each of the following "theorems" is true or false. Assume that a, b, c, d, and m are integers with m > 1. - $\text { If } a \equiv b ( \bmod m ) , \text { then } 2 a \equiv 2 b ( \bmod m )$

Encrypt the message KING using the RSA system with n = 43 · 61 and e = 13, translating each letter into integers (A = 00, B=01, . . . ) and grouping together pairs of integers.

suppose that a and b are integers, a ≡ 4 (mod 7), and b ≡ 6 (mod 7). Find the integer c with 0 ≤ c ≤ 6 such that - $c \equiv 5 b ( \bmod 7 )$

find the sum and product of each of these pairs of numbers. Express your answer as a binary expansion. - $( 101011 ) _ { 2 } , ( 1101011 ) _ { 2 }$

Find the prime factorization of 1,024.

determine whether each of the following "theorems" is true or false. Assume that a, b, c, d, and m are integers with m > 1. - $\text { If } a \equiv b ( \bmod m ) \text { and } c \equiv d ( \bmod m ) \text {, then } a c \equiv b + d ( \bmod m )$

Show that 7 is a primitive root of 13.

Decrypt the message EARLYL which is the ciphertext produced by encrypting a plaintext message using the transposition cipher with blocks of three letters and the permutation $\sigma$ of {1,2,3} defined by $\sigma$ (1)= 3 , $\sigma$ (2)=1 , and $\sigma$ (3)=2 .

find each of these values -(123 mod 19 · 342 mod 19) mod 19

Prove or disprove: For all integers $a , b \text {, if } a \mid b \text { and } b \mid a \text {, then } a = b \text {. }$

determine whether each of the following "theorems" is true or false. Assume that a, b, c, d, and m are integers with m > 1. - $\text { If } a \equiv b ( \bmod m ) \text {, and } a \equiv c ( \bmod m ) \text {, then } a \equiv b + c ( \bmod m ) \text {. }$

Applying the division algorithm with a = −41 and d = 6 yields what value of r?

Prove or disprove: For all integers $a , b , c , \text { if } a \mid c \text { and } b \mid c , \text { then } a b \mid c ^ { 2 }$

Solve the linear congruence 2x ≡ 5 (mod 9).

Find the sequence of pseudorandom numbers generated by the power generator $x _ { n + 1 } = x _ { n } ^ { 3 }$ and seed $x _ { 0 } = 3$

Convert (1 1101)₂ to base 10 .

Find gcd(2 $\left( 2 ^ { 89 } , 2 ^ { 346 } \right)$ by directly finding the largest divisor of both numbers.

Find 289 mod 17.

Prove or disprove: if p and q are prime numbers, then pq+1 is prime.