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:

  1. Let $p$ be a prime and define $n = p^2$.
    1. What is $\varphi(n)$? Write your answer as a polynomial in $p$.
    2. 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.

  2. Let $p$ and $q$ be distinct primes and define $n = pq$.
    1. What is $\varphi(n)$? Write your answer as a polynomial in $p$ and $q$, and then factor it.
    2. 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.

  3. 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.

  4. 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.)

  5. 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.

  6. 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.