##### Question

# 29. a) Use Fermat's Little Theorem to compute 5 2003 mod 7,

29. a) Use Fermat's Little Theorem to compute 5 2003 mod 7,

5 2003 mod 11, and 5 2003 mod 13.

b) Use your results from part (a) and the Chinese Re-

mainder Theorem to find 5 2003 mod 1001. (Note that

1 00 1 = 7 . 11 . 13.)

IGr Let n be a positive integer and let n – 1 = 2 S t, where s is a

nonnegative integer and t is an odd positive integer. We say

that n passes Miller's test for the base b if either b t = 1 (mod

n) or b 2Jt = -1 (mod n) for some j with 0 < j < s – 1. It

can be shown (see [Ro05]) that a composite integer n passes

Miller's test for fewer than n/4 bases b with 1 < b < n.

from discrete math and its appl.

chap 3.7 # 29

## Solutions

##### Expert Solution

No answers