365 Fall07 Final Solns

ÇANKAYA UNIVERSITY
Department of Mathematics and Computer Science
MATH 365
Elementary Number Theory I
FALL 2007
Final
SOLUTIONS
January 18, 2008
15:00-16:50
Surname :
Name :
ID # :
Department :
Section :
Instructor :
Signature :
• The exam consists of 6 questions.

• Please read the questions carefully and write your answers under the corresponding
questions. Be neat.
• Show all your work. Correct answers without sufficient explanation might not get full
credit.
• Calculators are not allowed.
GOOD LUCK!
Please do not write below this line.
Q1 Q2 Q3 Q4 Q5 Q6 TOTAL
20 20 20 20 20 10 110
1. Find all integer solutions to the congruence 42x ≡ 90 (mod 156).
Solutions:
By applying the Euclidean algorithm, we have
156 = 3 · 42 + 30
42 = 30 + 12
30 = 2 · 12 + 6
12 = 2·6
So gcd (42, 156) = 6, and we are expecting 6 incongruent solutions this congruence.
Now
6 = 30 − 2 · 12
= 30 − 2 (42 − 30)
= 3 · 30 − 2 · 42
= 3 (156 − 3 · 42) − 2 · 42
= (3) (156) − (11) (42) .
Multiplying both sides by 15, we get 90 = (45) (156) − (165) (42). So 90 ≡ −165 · 42 (mod 156),
which means −165 ≡ −9 (mod 156) is a solution. Therefore, the six solutions are given by
156
x = −9 + t, where t = 0, 1, · · · , 5, i.e., x ≡ −9, 17, 43, 69, 95, 121 (mod 156).
6
2. Find the 2 smallest positive integers x such that
x ≡ 2 (mod 7)
x ≡ 3 (mod 11)
x ≡ 4 (mod 13) .
Solution:
Obviously 7, 11, 13 are pairwise relatively prime, so by the Chinese Remainder Theorem (CRT)
this system has a unique solution mod 7 × 11 × 13 = 1001.
(11 × 13) b1 ≡ 1 (mod 7) ⇐⇒ 3b1 ≡ 1 (mod 7) ⇐⇒ b1 ≡ 5 (mod 7)
(7 × 13) b2 ≡ 1 (mod 11) ⇐⇒ 3b2 ≡ 1 (mod 11) ⇐⇒ b2 ≡ 4 (mod 11)
(7 × 11) b3 ≡ 1 (mod 13) ⇐⇒ −b3 ≡ 1 (mod 13) ⇐⇒ b3 ≡ −1 (mod 13)
and x ≡ (143) (5) (2) + (91) (4) (3) + (77) (−1) (4) ≡ 212 (mod 1001).
Thus the two solutions are 212 and 1213.
3.
a) Give a careful statement of Wilson’s Theorem.
b) Is 4 (29!) + 5! divisible by 31?
Solution:
(a) Wilson’s theorem: If p is prime, then
(p − 1)! ≡ −1 (mod p) .
(b) Since 31 is prime, it follows from Wilson’s theorem that

−1 ≡ 30! ≡ (29!) 30 ≡ (29!) (−1) (mod 31) .
Upon multiplying both sides by −1, we see that 29! ≡ 1 (mod 31) and so
4 (29!) + 5! ≡ 4 (1) + 120 ≡ 124 ≡ 4 · 31 ≡ 0 (mod 31) .
4.
(a) Add two negative integeres to the set {6, 11, 14, 28} so that the six integers you have will
form a complete residue system modulo 6. Justify your answer.
b) Does 41 divide 7 · 320 + 6?
Solution:
(a) A complete residue system modulo 6 is a set of six integers in which no two are congruent
to each other. Note that
6 ≡ 0 (mod 6)
11 ≡ 5 (mod 6)
14 ≡ 2 (mod 6)
28 ≡ 4 (mod 6) .
So we need to find two negative integers which are congruent to 1 and 3 modulo 6. Since
−5 ≡ 1 (mod 6) and −3 ≡ 3 (mod 6), the numbers 6, 11, 14, 28, −5, −3 form a complete residue
system modulo 6.
(b) We want to find out whether 7 · 320 + 6 ≡ 0 (mod 41) .
Note that 34 = 81 ≡ −1 (mod 41). So 320 ≡ (−1)5 ≡ −1 (mod 41). Thus 7·320 +6 ≡ 7 (−1)+6 ≡
−1 (mod 41). Since −1 ≡ 0 (mod 41), 41 does not divide 7 · 320 + 6.
5. Break the modulus into prime powers to find the least complete solution.
4x2 − 12x + 5 ≡ 0 (mod 77) .
Solution: The prime power factors of 77 are 7 and 11. By testing values in complete residue
systems we find that a complete solution to
4x2 + 2x + 5 ≡ 0 (mod 7)
is x = −3, −1; and a complete solution to
4x2 − x + 5 ≡ 0 (mod 11)
is x = −3, 6.
Now we use the Chinese Remainder Theorem (CRT) to solve the simultaneous congruences
x ≡ −3 or − 1 (mod 7)
x ≡ −3 or 6 (mod 11) ,
which involves solving
11x1 ≡ 1 (mod 7)
7x2 ≡ 1 (mod 11)
Solutions are x1 = 2 and x2 = −3 (mod 11). Then by the CRT, the simultaneous solutions are
x = (11) (2) (−3 or − 1) + (7) (−3) (−3 or 6)
= −192, −148, −3, 41
This is a complete solution to the original congrunce. The least complete solution is x =
6, 38, 41, 74.
6. (Bonus) Find all solutions to the following system of congruences.
x ≡ 34 (mod 105)
x ≡ 79 (mod 330)
Solution: Since 105 = 3 × 5 × 7 and 330 = 2 × 3 × 5 × 11, this system is equivalent to
x ≡ 34 (mod 3)
x ≡ 34 (mod 5)
x ≡ 34 (mod 7)
x ≡ 79 (mod 2)
x ≡ 79 (mod 3)
x ≡ 79 (mod 5)
x ≡ 79 (mod 11) .
Reducing modulo the respective modulus, we get
x ≡ 1 (mod 3)
x ≡ 4 (mod 5)
x ≡ 6 (mod 7)
x ≡ 1 (mod 2)
x ≡ 1 (mod 3)
x ≡ 1 (mod 5)
x ≡ 2 (mod 11) .
So we are left with
x ≡ 1 (mod 2)
x ≡ 1 (mod 3)
x ≡ −1 (mod 5)
x ≡ −1 (mod 7)
x ≡ 2 (mod 11) .
Now we need to solve
3 × 5 × 7 × 11b1 ≡ 1 (mod 2) , 2 × 5 × 7 × 11b2 ≡ 1 (mod 3) , 2 × 3 × 7 × 11b3 ≡ 1 (mod 5)
2 × 3 × 5 × 11b4 ≡ 1 (mod 7) , 2 × 3 × 5 × 7b5 ≡ 1 (mod 11) .
Reducing modulo the respective modulus, we get
b1 ≡ 1 (mod 2) , −b2 ≡ 1 (mod 3) , 2b3 ≡ 1 (mod 5)
b4 ≡ 1 (mod 7) , b5 ≡ 1 (mod 11) .
Multiply suitable numbers on both side of the equivalence to reduce the coefficients of bi to 1.
b1 ≡ 1 (mod 2) , b2 ≡ −1 (mod 3) , b3 ≡ 3 (mod 5)
b4 ≡ 1 (mod 7) , b5 ≡ 1 (mod 11) ,
So
x ≡ 3 × 5 × 7 × 11 × 1 × 1 × +2 × 5 × 7 × (−1) × 1 + 2 × 3 × 7 × 11 × 3 × (−1)
+2 × 3 × 5 × 11 × 1 × (−1) + 2 × 3 × 5 × 7 × 1 × 2 (mod 2 × 3 × 5 × 7 × 11)
≡ −911 (mod 2310) .
Check that −911 ≡ 349 (mod 105) and −911 ≡ 79 (mod 330).

365 Fall07 Final Solns

Uploaded by

Copyright:

Available Formats

365 Fall07 Final Solns

Uploaded by

Document Information

Original Description:

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

365 Fall07 Final Solns

Uploaded by

Copyright:

Available Formats

ÇANKAYA UNIVERSITY

Department of Mathematics and Computer Science

• The exam consists of 6 questions.

(b) Since 31 is prime, it follows from Wilson’s theorem that

You might also like