MATH 319 Exercise on Congruences and Fermat’s Theorem
Names______________________________________________________
1.
Use
the program GCD2 to solve the following congruences (if possible):
a) 
x = ____________
b)
x = ____________
c)
x = ____________
d)
x = ____________
e)
x = ____________
2.
Find
a Reduced Residue System modulo 30 from the set {1,2,3,…,30}.
{________________________}
In Maple the function modp(a,b) produces an integer c that is
congruent to a mod b with 
. Multiply all the
elements of your RRS by 71 and using modp reduce them mod 30. This should yield the same RRS in a
different order.
{____________________________}.
=____________.
3. Recall the first part of Fermat’s
Theorem: If p is a prime and (a,p) =1
then 
. Compute 
for each of the
following pairs of a and p. In Maple
the operator &^ will perform the exponentiation very quickly. For example modp(3&^100,101) computes 
.
|
a |
p |
|
a |
p |
|
|
2 |
89 |
|
3 |
89 |
|
|
2 |
161 |
|
7 |
89 |
|
|
2 |
341 |
|
3 |
341 |
|
|
2 |
561 |
|
7 |
561 |
|
|
2 |
1005 |
|
3 |
91 |
|
|
2 |
1105 |
|
19 |
561 |
|
Not
all the p’s listed are primes. Which
ones can you tell are not primes by looking at your calculations?
________________
Load
the Number Theory package ( use with(numtheory);)
and use the function ifactor to determine which of the p’s are primes.
__________________
4. Maple has the function phi which computes 
, the number of numbers in a RRS mod n. Euler generalized Fermat’s Theorem for
non-primes.
Theorem (Euler’s Generalization) Let n be greater than 1 and (a,n) = 1. Then 
Compute
for a = 2 and n =
1101 and for a =2 and n =230-1.
____________,_____________