Scribd
Upload
89 views1 page

Solving Linear Congruences and Diophantine Equations

This document contains problems involving modular arithmetic and congruences. It includes problems solving linear congruences, Diophantine equations using congruences, simultaneous congruences, proving conditions for simultaneous solutions of congruences, applying Fermat's theorem, and establishing statements about pseudoprimes.

Uploaded by

Huang ShangTing
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOC, PDF, TXT or read online on Scribd
89 views1 page

Solving Linear Congruences and Diophantine Equations

This document contains problems involving modular arithmetic and congruences. It includes problems solving linear congruences, Diophantine equations using congruences, simultaneous congruences, proving conditions for simultaneous solutions of congruences, applying Fermat's theorem, and establishing statements about pseudoprimes.

Uploaded by

Huang ShangTing
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOC, PDF, TXT or read online on Scribd

Problems 4.

4
1. Solve the following linear congruence:
(e) 34 x ≡ 60(mod 98)
(f) 140 x ≡ 133(mod 301) (Hint: gcd(140,301) = 7 )

2. Using congruence, solve the Diophantine equations below:


(c) 5 x − 53 y ≡ 17

4. Solve each of the following sets of simultaneous congruence:


(c) x ≡ 5(mod 6), x ≡ 4(mod11), x ≡ 3(mod17) .

11. Prove that the congruence: x ≡ a(mod n) and x ≡ b(mod m) admit a simultaneous
solution if and only if gcd(n, m) a − b ; If a solution exists, confirm that it is unique
modulo lcm(n, m) .

Problems 5.2
12 n + 6
3. From Fermat’s theorem deduce that, for any integer n ≥ 0, 1311 +1.

10. Assuming that a and b are integers not divisible by the prime p , establish the
following:
(a) If a p ≡ b p (mod p), then a ≡ b(mod p)
(b) If a p ≡ b p (mod p), then a p ≡ b p (mod p 2 )
(There’s a “Hint” in the textbook following the question.)

11. Employ Fermat’s theorem to prove that, if p is an odd prime, then


(a) 1 p −1 + 2 2− p +  ( p − 1) p −1 ≡ −1(mod p )
(b) 1 p + 2 2 +  ( p − 1) p ≡ 0(mod p)
(There’s a “Hint” in the textbook following the question)

15 Establish the statements below:


(a) If the number M p = 2 − 1 is composite, where p is a prime, then M p is a pseudo
p

prime.
(b) Every composite number Fn = 2 2 + 1 is a pseudo prime. (n = 0,1,2 )
n

n n +1
n +1 2
(Hint: By Question 21 of Section 2.3, 2 2 implies that 2
2
− 1 2 Fn −1 − 1; but
n +1
Fn 2 2 − 1;

Problems 5.3
5. (a) Prove that an integer n > 1 is prime if and only if (n − 2)!≡ 1(mod n) .
(b) If n is a composite integer, show that (n − 1)!≡ 0(mod n), except when n = 4 .

You might also like