Let $a,b,p\in\mathbb Z$ and $n\in\mathbb N$ Show that $a\equiv b\pmod n$ is an equivalence relation.

Question

Let $a,b,p\in\mathbb Z$ and $n\in\mathbb N$

(a) Show that the relation defined by $a\sim b$ if $a\equiv b\pmod n$ is an equivalence relation. For the purposes of this exercise use Definition 2.1.3 of $a\equiv b\pmod n$.

(b) Suppose $p$ is prime, and suppose $a\in\mathbb Z_p\setminus\{0\}$. Show that $a^{-1}$ exists. Then show $|\mathbb Z_p^\times|=p-1$.

(c) Find $\mathbb Z^\times_{105}$

[original image]

I was just wondering if anyone could help me with part a on this question as i seem to be stuck, would the relation be reflexive, and how would one go about showing this as i haven't yet came across an example like this before.

For part b to show that $a^{-1}$ would you need to show that $gcd(a,p)=1$ (or is there an easier way) and how would you then show that the magnitude of the set is p-1.

I think I have done part c correctly it is just calculating the gcd of the individual elements up to 105 with 105 for example if $gcd(y,105)=1$ then $y$ is an element in the set we are trying to construct thanks for taking time to read this looking forward to the responses.

(from duplicate question):

for showing that the magnitude of the set is p-1 is this just to do with the definition of a prime number as the only number in that set that is not coprime with p is p itself

for part C i got 48 elements in the set but it would take to long to list them here.

Answer 1

Let $a,b,p\in\mathbb Z$ and $n\in\mathbb N$

(a) Show that the relation defined by $a\sim b$ if $a\equiv b\pmod n$ is an equivalence relation.

We need to show that the relation is reflexive, symmetric and transitive. I'm using the definition you see on the first line of the symmetric argument.

• Reflexive $: \\a=a \implies a\equiv a \bmod n \therefore a\sim a \quad \checkmark$

• Symmetric $: \\ a\equiv b \bmod n \iff \exists k\in \mathbb Z: a = b +kn \\ \implies b=a+(-k)n \implies b\equiv a \bmod n \therefore a\sim b \implies b\sim a \quad \checkmark$

• Transitive $: \\ a\equiv b \bmod n \text{ and }b\equiv c \bmod n \implies \exists k_1,k_2\in \mathbb Z: a = b +k_1n, b = c +k_2n\\ \implies a=c+(k_1+k_2)n \implies a\equiv c \bmod n \\ \therefore a\sim b \ \land\ b\sim c \implies a\sim c \quad \checkmark$

(b) Suppose $p$ is prime, and suppose $a\in\mathbb Z_p\setminus\{0\}$. Show that $a^{-1}$ exists. Then show $|\mathbb Z_p^\times|=p-1$.

Consider two numbers $b,c \in\mathbb Z_p\setminus\{0\}$ . Then $b\ne c \implies b-c \ne 0 \implies a(b-c) \ne 0$ $ \implies ab-ac \ne 0 \implies ab \ne ac$ . So the $p\mathord{-}1$ members of $\mathbb Z_p\setminus\{0\}$ give $p\mathord{-}1$ different results multiplied to $a$, that is, the full set. In particular one such $d$ must give $ad =1$ so $a$ has an inverse, and since $a$ was a general choice, all members of the set are units and $|\mathbb Z_p^\times|=p-1$

(c) Find $\mathbb Z^\times_{105}$

As above all coprime members of the set will form a closed set under multiplication since factors of $105 = 3\cdot 5\cdot 7$ will not appear by multiplying numbers that do not contain them. There are $(3\mathord{-}1)(5\mathord{-}1)(7\mathord{-}1) = 48$ such numbers $<105$ so $|\mathbb Z^\times_{105}|=48$, consisting of the powers of two, primes $11$ and upwards and $2,4, 8$ times those primes as approriate.