Math 120B HW 3
Due Tuesday, April 21.
Note that for all positive integers $n$ and $k$, and all integers $a$ that are relatively prime to $n$, Euler's theorem gives
$$a^{k\varphi(n)+1} \equiv (a^{\varphi(n)})^k \cdot a \equiv 1^k \cdot a \equiv a \pmod{n},$$
In the special case that $n$ is prime, the hypothesis
that $a$ is relatively prime to $n$ is unnecessary: otherwise
$a$ is divisible by $n$, which implies that $$a^{k\varphi(n)+1} \equiv
0^{k\varphi(n)+1} \equiv 0 \equiv a \pmod{n}.$$
The first two problems ask whether $a^{k\varphi(n)+1} \equiv a \pmod{n}$ in some other special cases.
Problems:
- Let $p$ be a prime and define $n = p^2$.
- What is $\varphi(n)$? Write your answer as a polynomial in $p$.
- Is it true that $a^{k\varphi(n)+1} \equiv a \pmod{n}$ for every integer $a$ and every positive integer $k$?
Justify your answer for each part.
- Let $p$ and $q$ be distinct primes and define $n = pq$.
- What is $\varphi(n)$? Write your answer as a polynomial in $p$ and $q$, and then factor it.
- Is it true that $a^{k\varphi(n)+1} \equiv a \pmod{n}$ for every
integer $a$ and every positive integer $k$?
Hint: because $p$ and $q$ are relatively prime, two integers are congruent modulo $pq$ if and only if they are congruent modulo $p$ and also congruent modulo $q$.
Justify your answer for each part.
- Let $p$ and $q$ be distinct primes and define $n = pq$. Let $e \in \mathbb{Z}_{\varphi(n)}$
and define a function $\operatorname{enc} : \mathbb{Z}_n \to \mathbb{Z}_n$
by $\operatorname{enc}(a) = a^e \bmod n$.
Prove that if $e$ has an inverse in $\mathbb{Z}_{\varphi(n)}$, then the function $\operatorname{enc}$ has an inverse.
Hint: you can undo the operation of raising $a$ to the $e^\text{th}$
power by raising to a further power.
- Let $R$ be a commutative ring with unity $1 \ne 0$
and define a binary relation $\sim$ on $R \times R^*$ (where $R^*$ denotes the set of all nonzero elements of $R$) by $(a,b) \sim (c,d) \iff ad = bc$.
Prove that if $R$ is not an integral domain, then the relation $\sim$ is not transitive.
(This will show one reason why the construction of a field of quotients that we discussed only works for integral domains.)
- Let $D$ be an integral domain and let $F$ be a field of quotients
of $D$ (in the abstract sense.) Prove that if $D$ itself is a field,
then $D \cong F$.
Hint: to say that $F$ is a field of quotients of $D$
means that there is an injective homomorphism $i : D \to F$ such that
$F = \{i(a)i(b)^{-1} : a \in D \mathbin{\And} b \in D^*\}$. Prove that if $D$
is a field, then such a function $i$ must be surjective also.
- Let $D$ be an integral domain, let $F$ be a field, and let $i : D \to F$ be an injective homomorphism.
Define the set
$$ K = \{i(a)i(b)^{-1} : a \in D \mathbin{\And} b \in D^*\} \subseteq F.$$
Prove that $K$ is a field of quotients of $D$ (in the abstract sense.)
Hint: you only have to prove that $K$ is a subfield of $F$. You can do this by showing that it contains $0_F$ and $1_F$ and satisfies certain closure properties.