Let p= 11 and 13. (a) Determine all the squares modulo p in
(Z/pZ)∗. (b) Using...
Let p= 11 and 13. (a) Determine all the squares modulo p in
(Z/pZ)∗. (b) Using this determine the value of the Legendre
symbol(a/p)for all a∈(Z/pZ)∗. (c) For all a∈(Z/pZ)∗, compute
a^((p−1)/2) and confirm that a^((p−1)/2)=(a/p).
1. (a) Let p be a prime. Prove that in (Z/pZ)[x],
xp−x= x(x−1)(x−2)···(x−(p−1)).
(b) Use your answer to part (a) to prove that for any prime p,
(p−1)!≡−1 (modp).
Let ∼ be the relation on P(Z) defined by A ∼ B if and only if
there is a bijection f : A → B. (a) Prove or disprove: ∼ is
reflexive. (b) Prove or disprove: ∼ is irreflexive. (c) Prove or
disprove: ∼ is symmetric. (d) Prove or disprove: ∼ is
antisymmetric. (e) Prove or disprove: ∼ is transitive. (f) Is ∼ an
equivalence relation? A partial order?
Consider these 2 functions (all with domain and codomain (Z/pZ)
for some big prime p): h(x) = 1492831*x and h(x) = x3 .
Why are these bad cryptographic hash functions? Give different
reasons for the two.
Let p be an odd prime.
(a) (*) Prove that there is a primitive root
modulo p2 . (Hint: Use that if a, b have orders n, m,
with gcd(n, m) = 1, then ab has order nm.)
(b) Prove that for any n, there is a primitive
root modulo pn.
(c) Explicitly find a primitive root modulo
125.
Please do all parts.
Thank you in advance
1. Determine an inverse of a modulo m for a =
6 and m = 11. This is equivalent to
answering the question “_______ is the unique inverse of
6 (mod 11) that is non-negative and <
11.” Show your work following the
steps.
Beside the inverse you identified in part a), identify two
other inverses of 6 (mod 11).
Hint: All of these inverses are congruent to each
other mod 11.
Although the congruence can be solved using any of the inverses...
(A) Let a,b,c∈Z. Prove that if gcd(a,b)=1 and a∣bc, then
a∣c.
(B) Let p ≥ 2. Prove that if 2p−1 is prime, then p
must also be prime.
(Abstract Algebra)
Find all primitive roots:
(a) modulo 25, or show that there are none
(b) modulo 34, or show that there are none
(c) Assuming that 2 is a primitive root modulo 67, find all
primitive roots modulo 67.
Suppose A = {(a, b)| a, b ∈ Z} = Z × Z. Let R be the relation
define on A where (a, b)R(c, d) means that 2 a + d = b + 2 c.
a. Prove that R is an equivalence relation.
b. Find the equivalence classes [(−1, 1)] and [(−4, −2)].