Prove that for all integers x, if x is not divisible by 7, then x^3 ≡ 1 mod 7 or x^3 ≡ −1 mod 7.
1. Show, using modular arithmetic, that for all n ∈ N, 3(7^3n) + 2^n+3 is divisible by 11.
2. Prove that for all integers x,
if x is not divisible by 7, then x^3 ≡ 1 mod 7 or x^3 ≡ −1 mod 7.
Hint: There are 6 cases to consider.
3. Prove or disprove each of the following two statements.
(i) For all integers x and y and natural numbers n,
if xy ≡ 0 mod n, then x ≡ 0 mod n or y ≡ 0 mod n.
(ii) For all natural numbers n > 4 and integers x, if x^2 ≡ 4 mod n, then x ≡ 2 mod n.
4. Fermat’s Little Theorem says that for all natural numbers p and integers x, if p is prime then x^p ≡ x mod p.
(i) Show that the statement is wrong if we drop the assumption that p is prime.
[Remember: All you need to do is to give a counterexample.]
(ii) Show, by giving an example, that if p is not prime, then x^p ≡ x mod p can still be true for some integers x with x is not −1, 0, 1.
Trending now
This is a popular solution!
Step by step
Solved in 3 steps
by Bartleby Expert
