Math 361, Spring 2016, Assignment 1

Carefully define the following terms, then give one example and one non-example of each:

1. Unit (of a unital ring).
2. Zero-divisor.
3. Field.
4. (Integral) domain.
5. Group of units (of a unital ring).
6. Euler totient function.

Carefully state the following theorems (you do not need to prove them):

1. Theorem relating fields to integral domains.
2. Theorem concerning the group of units of a product ring.
3. Chinese Remainder Theorem (ring version).
4. Formula for $\phi(ab)$ when $a$ and $b$ are relatively prime.
5. Formula for $\phi(p^n)$ when $p$ is prime.
6. Euler's Theorem.
7. Fermat's Little Theorem.

Solve the following problems:

1. Section 20, problems 1, 5, 7, 9, and 10.

--------------------End of assignment--------------------

Solutions:

Vocab

1. A ring is unital provided it has an identity. (Fun fact, the identity is called the unity, not unit) If an element of such a ring has a multiplicative inverse, that element is a unit.

   e.g. In $(\mathbb{Q}, +, \cdot)$, the element $\frac{19}{1}$ is a unit, because it has inverse $\frac{1}{19}\in\mathbb{Q}$.

   $\neg$e.g. In $(\mathbb{Z}, +, \cdot)$, the element $19$ is not a unit, because nothing multiplied by $19$ can produce the identity.

2. A zero divisor is a nonzero element $a$ such that $\exists b \neq 0$ with $ab = 0$ or $ba = 0$. (The kicker being you can get the zero element without actually multiplying by $0$)

   e.g. In $(\mathbb{Z}_4, +, \cdot)$, $2$ is a zero divisor, because $2\cdot2=4=0$.

   $\neg$e.g. In the same ring, $3$ is not a zero divisor: $3\cdot1\neq0$, $3\cdot2\neq0$, $3\cdot3\neq0$.

3. A field is a unital ring of which every nonzero element is a unit (note: this property alone defines a division ring), the second binary operation ("multiplication") of which is commutative.

   e.g. $(\mathbb{Q}, +, \cdot)$

   $\neg$e.g. $(\mathbb{Z}, +, \cdot)$

4. An integral domain (often referred to as domain) is a commutative, unital ring with no zero divisors.

   e.g.Any field is a domain.

   $\neg$e.g. From the top example in number 2, $(\mathbb{Z}_4)$ is almost a domain, if it weren't for that pesky $2$.
5. The units of a unital ring form a group under multiplication. This group is called the group of units.

   e.g. Back in $(\mathbb{Z}_4, +, \cdot)$, the units are $1$ ($1\cdot1=1$) and $3$ ($3\cdot3=1$), and so the group of units of $(\mathbb{Z}_4, +, \cdot)$ is the group $(\{1, 3\}, \cdot)$.

   $\neg$e.g. The group of units of $(\mathbb{Z}_4, +, \cdot)$ is not $(\{0, 1, 3)\}, \cdot)$, because $0$ is not a unit.

6. The Euler totient function is the function $\varphi:\mathbb{Z}^+\to\mathbb{Z}^+$, whose output for $n\in\mathbb{Z}^+$ is the cardinality of the group of units of $(\mathbb{Z}_n, +, \cdot)$.

   e.g. $\varphi(5)=4$, because the units of $(\mathbb{Z}_5, +, \cdot)$ are $1, 2, 3$ and $4$. Those are four numbers $\Box$

   $\neg$e.g. $\varphi(4)=3$ is not a true statement. As discussed earlier, the units of $(\mathbb{Z}_4, +, \cdot)$ include $1$ and $3$. Those are two numbers, not enough to be three numbers.

Theorems

1. Any given field is also an integral domain.
2. Let $R$ and $S$ be unital rings, and let $G(R)$ and $G(S)$ be their respective groups of units. Then the group of units of $R\times S=G(R)\times G(S)$.
3. $(\mathbb{Z}_a, +, \cdot)\times(\mathbb{Z}_b, +, \cdot)$ is isomorphic to $(\mathbb{Z}_{ab}, +, \cdot)$ if and only if gcd($a, b$)$=1$. (In other words, "... if and only if $a$ and $b$ are relatively prime)
4. If $a$ and $b$ are relatively prime, $\varphi(a\cdot b)=\varphi(a)\cdot\varphi(b)$, where $\cdot$ is standard, familiar, default, natural integer multiplication.
5. (Euler) If $p$ is any prime number and $n$ is any positive integer, $\varphi(p^n)=p^n-p^{n-1}$
6. (Fermat)Suppose $n$ is a positive integer and $a$ and $n$ are relatively prime. Then $a^{\varphi(n)}\equiv1\mod{n}$

Book Problems

1. Find a generator for the group $(\mathbb{Z}_7, \cdot)$

Solution: $3$ generates the multiplicative group. The powers of $3$ starting at $1$ are: $3, 2, 6, 4, 5, 1, ...$

5. Find the remainder of $37^{49}$ when it is divided by $7$

Solution: $37\equiv2\mod{7}$, so $37^{49}\equiv2^{49}\mod{7}$.

$2^{49}=2^48\cdot2=2(2^6)^8$.

Using Fermat's theorem with $a=2$ and $p=7$, $2^6\equiv1\mod{7}$.

Making this substitution, $2\cdot(1^6)^8=2\cdot1\equiv2\mod{7}$. The remainder is thus $2$.

7. Make a table of values for $\varphi(x)$ for $x\leq30$

Solution:

$x$	$\varphi(x)$
$2$	$1$
$3$	$2$
$4$	$2$
$5$	$4$
$6$	$2$
$7$	$6$
$8$	$\varphi(2^3)=2^3-2^2=4$
$9$	$\varphi(3^2)=3^2-3=6$
$10$	$\varphi(5)\cdot\varphi(2)=4$
$11$	$10$
$12$	$\varphi(3)\cdot\varphi(4)=4$
$13$	$12$
$14$	$\varphi(7)\cdot\varphi(2)=6$
$15$	$\varphi(5)\cdot\varphi(3)=8$
$16$	$\varphi(2^4)=16-8=8$
$17$	$16$
$18$	$\varphi(3^2)\cdot\varphi(2)=6$
$19$	$18$
$20$	$\varphi(4)\cdot\varphi(5)=8$
$21$	$\varphi(3)\cdot\varphi(7)=12$
$22$	$\varphi(2)\cdot\varphi(11)=10$
$23$	$22$
$24$	$\varphi(4)\cdot\varphi(3)\cdot\varphi(2)=4$
$25$	$\varphi(5^2)=25-5=20$
$26$	$\varphi(13)\cdot\varphi(2)=12$
$27$	$\varphi(3^3)=27-9=18$
$28$	$\varphi(7)\cdot\varphi(4)=12$
$29$	$28$
$30$	$\varphi(5)\cdot\varphi(3)\cdot\varphi(2)=8$

9. Compute $\varphi(p\cdot q)$, where $p$ and $q$ are prime

Solution: If $p$ and $q$ are equal, then Euler's theorem applies. In this case, $\varphi(p\cdot q)=\varphi(p^2)=p^2-p$.

If $p\neq q$, then gcd($p, q$)$=1$, and so $\varphi(p\cdot q)=\varphi(p)\varphi(q)$. Furthermore, since $p$ and $q$ are prime, this can be evaluated to $(p - 1)(q - 1)$.

10. Find the remainder of $7^{1000}$ when divided by $24$

Solution: By Euler's Pertinent Theorem, with $a=7$ and $n=24$, $7^{\varphi(24)}\equiv1\mod{24}$. Therefore, $7^8\equiv1\mod{24}$.

$1000=8\cdot125$, so $7^{1000}=(7^8)^{125}$. In mod $24$, $(7^8)^{125}=1^{125}=1$. Thus, $7^{1000}\div24$ has remainder $1$.