Math 120B HW 3 Solutions

1. Let $p$ be a prime and define $n = p^2$.

   1. $\varphi(n) = p^2 - p$ because the set $\{0,\ldots,n-1\}$ has $p^2$ many elements, and it has $p$ many elements that are not relatively prime to $p^2$, namely $0,p,2p,\ldots,(p-1)p$. (It's convenient to start at zero here; note that zero is relatively prime to every number except $1$.)

   2. This is false. Consider the case $p = 2$, $n = 4$, $a = 2$, $k = 1$. Then $a^{k\varphi(n)+1} = a^{2+1} = 2^3 \not\equiv 2 \pmod{4}$.

2. Let $p$ and $q$ be distinct primes and define $n = pq$.

   1. $\varphi(n) = pq - p - q + 1 = (p-1)(q-1)$. This is because an integer is relatively prime to $pq$ if and only if it is not divisible by $p$ or by $q$. In the set $\{0,\ldots,pq-1\}$ there are $pq$ many elements in total, $q$ many elements divisible by $p$, $p$ many elements divisible by $q$, and $1$ element divisible by both $p$ and $q$ (namely $0$.)

      (This also follows from the general fact that if $r$ and $s$ are relatively prime then $\varphi(rs) = \varphi(r)\varphi(s)$, which we haven't talked about in class.)

   2. This is true. Let $a$ be an integer and let $k$ be a positive integer. We claim that $a^{k(p-1)(q-1)+1} \equiv a \pmod{n}$. Because $n = pq$ and $p$ and $q$ are relatively prime, any integer is divisible by $n$ if and only if it is divisible by both $p$ and $q$. Therefore it suffices to prove the two congruences $a^{k(p-1)(q-1)+1} \equiv a \pmod{p}$ and $a^{k(p-1)(q-1)+1} \equiv a \pmod{q}$.

      In other words, it suffices to prove the two congruences $(a^{p-1})^{k(q-1)} \cdot a \equiv a \pmod{p}$ and $(a^{q-1})^{k(p-1)} \cdot a \equiv a \pmod{q}$. The first congruence is clearly true when $a$ is divisible by $p$ and is true when $a$ is not divisible by $p$ by Fermat's little theorem. Similarly, the second congruence is clearly true when $a$ is divisible by $q$ and is true when $a$ is not divisible by $q$ by Fermat's little theorem.

3. If $e$ has an inverse $d$ in $\mathbb{Z}_{\varphi(n)}$, then this means that when we multiply $e$ and $d$ as integers we get $ed = k\varphi(n) + 1$ for some $k$. Define the function $\operatorname{dec} : \mathbb{Z}_n \to \mathbb{Z}_n$ by $\operatorname{dec}(a) = a^d \bmod n$. Then for all $a \in \mathbb{Z}_n$ we have \[ \operatorname{dec}(\operatorname{enc}(a)) \equiv (a^e)^d \equiv a^{ed} \equiv a^{k\varphi(n) + 1} \equiv a \pmod n\] by problem 2b, so $\operatorname{dec} \circ \operatorname{enc}$ is the identity function on $\mathbb{Z}_n$. A similar argument shows that $\operatorname{enc} \circ \operatorname{dec}$ is the identity function on $\mathbb{Z}_n$, so the function $\operatorname{dec}$ is the inverse of the function $\operatorname{enc}$.

   (I called the functions "enc" and "dec" because they are the encryption and decryption functions used in RSA.)

4. Let $R$ be a commutative ring with unity $1 \ne 0$. If $R$ is not an integral domain, then we can take nonzero elements $a$ and $b$ of $R$ such that $ab = 0$. Then we have $(1,a) \sim (b,0)$ because $1 \cdot 0 = 0 = ab$, and we have $(b,0) \sim (1,0)$ because $b \cdot 0 = 0 = 0 \cdot 1$, but $(1,a) \not\sim (1,0)$ because $1 \cdot 0 = 0 \ne a = a \cdot 1$. Therefore the relation $\sim$ is not transitive.

5. Because $F$ is a field of quotients of $D$, we can take an injective homomorphism $i : D \to F$ such that $F = \{i(a)i(b)^{-1} : a \in D \mathbin{\And} b \in D^*\}$. We claim that $i$ is surjective (and is therefore an isomorphism.)

   Let $c \in F$, say $c = i(a)i(b)^{-1}$ where $a \in D$ and $b \in D^*$. Because $D$ is a field it has an element $ab^{-1}$, and $i(ab^{-1}) = i(a)i(b^{-1}) = i(a)i(b)^{-1} = c$.

6. Given such a function $i : D \to F$, to show that $K$ is a field of quotients of $D$ we only need to show that $K$ is a field. We will show this by showing that $K$ is a subfield of $F$.

   First we show that $K$ contains the additive and multiplicative identity elements:

   • $0_F = i(0_D)i(1_D)^{-1} \in K$, and

   • $1_F = i(1_D)i(1_D)^{-1} \in K$.

   Next we show closure under addition and multiplication. Consider two arbitrary elements of $F$, which have the form $i(a)i(b)^{-1}$ and $i(c)i(d)^{-1}$ where $a,c \in D$ and $b,d \in D^*$. Note that the product $bd$ is nonzero, so it is also in $D^*$, and it follows that $i(bd)$ is nonzero because $i$ is injective. We have

   • $i(a)i(b)^{-1} + i(c)i(d)^{-1} = (i(a)i(d) + i(b)i(c))i(b)^{-1}i(d)^{-1} = i(ad + bc)i(bd)^{-1} \in K$, and

   • $i(a)i(b)^{-1} \cdot i(c)i(d)^{-1} = i(a)i(c)i(b)^{-1}i(d)^{-1} = i(ac)i(bd)^{-1} \in K$.

   Finally, we show closure under additive inverses and under multiplicative inverses for nonzero elements. Consider an arbitrary element of $F$, which has the form $i(a)i(b)^{-1}$ where $a \in D$ and $b \in D^*$. We have

   • $-i(a)i(b)^{-1} = i(-a)i(b)^{-1} \in K$, and

   • $(i(a)i(b)^{-1})^{-1} = (i(b)^{-1})^{-1}i(a)^{-1} = i(b)i(a)^{-1} \in K$ if $i(a)i(b)^{-1}$ is nonzero.

   (Note that if $i(a)i(b)^{-1}$ is nonzero, then $i(a)$ is nonzero so $i(a)^{-1}$ makes sense, and also $a$ is nonzero so $a \in D^*$.)