Abstract Nonsense

Crushing one theorem at a time

Dummit and Foote Preliminaries Sections .1,.2, and .3


In exercises 1 to 4 let \mathcal{A} be the set of all 2\times 2 matrices with real number entries. Recall that matrix multiplication is defined by

\begin{bmatrix}a & b\\ c& d\end{bmatrix}\begin{bmatrix}p & q\\ r & s\end{bmatrix}=\begin{bmatrix} ap+br & aq+bs\\ cp+dr & cq+ds \end{bmatrix}

Let

M=\begin{bmatrix}1 & 1\\ 0 & 1 \end{bmatrix}

and

\mathcal{B}=\left\{X\in\mathcal{A}:MX=XM\right\}

1.

Problem: Determine which of the following matrices lie in \mathcal{B}

a) M

b) \begin{bmatrix}1 & 1\\ 1&1 \end{bmatrix}

c) \begin{bmatrix}0 & 0\\ 0& 0\end{bmatrix}

d) \begin{bmatrix} 1 &1 \\ 1 &0 \end{bmatrix}

e) I (the identity)

f) \begin{bmatrix}0 & 1\\ 1& 0\end{bmatrix}

Solution:

a) Clearly M\in\mathcal{B} since MM=MM

b) No.

c) Clearly this will commute with M.

d) Doesn’t commute.

e) Clearly this commutes, it’s the identity matrix.

f) Doesn’t commute.

2.

Problem: Prove that if P,Q\in\mathcal{B} then P+Q\in\mathcal{B}

Proof: Note that

\left(P+Q\right)M=PM+QM=MP+MQ=M\left(P+Q\right)

The conclusion follows.

3.

Problem: Prove that if P,Q\in\mathcal{B} then PQ\in\mathcal{B}

Proof: Merely note that

\left(PQ\right)M=P\left(QM\right)=P\left(MQ\right)=\left(PM\right)Q=\left(MP\right)Q=M\left(PQ\right)

from where the conclusion follows.

4.

Problem: Find the conditions on p,q,r,s which determine when \begin{bmatrix}p & q \\ r & s\end{bmatrix}=P\in\mathcal{B}

Proof: A simple calculations shows that

PM-MP=\begin{bmatrix} r & s-p \\ 0 & -r\end{bmatrix}

And since evidently

X\in \mathcal{B}\Leftrightarrow XM-MX=0

It follows that

P\in\mathcal{B}\Leftrightarrow r=0\text{ and }s=p

5.

Problem: Determine whether the following functions f are well-defined:

a) \displaystyle f:\mathbb{Q}\to\mathbb{Z}:\frac{a}{b}\mapsto a

b) \displaystyle f:\mathbb{Q}\to\mathbb{Q}:\frac{a}{b}\mapsto\frac{a^2}{b^2}

Proof:

a) Clearly this is not well defined since

\displaystyle \frac{1}{2}=\frac{2}{4},\text{ but }f\left(\frac{1}{2}\right)=1\ne2=f\left(\frac{2}{4}\right)

b) This is well-defined, to see this note that

\frac{a}{b}=\frac{c}{d}\implies \frac{a^2}{b^2}=\frac{c^2}{d^2}

6.

Problem: Determine whether the function f:\mathbb{R}\to\mathbb{N} defined by mapping a real number to the first digit of its decimal point expansion is well-defined.

Proof: This problem is deliberately meant to trip you up. The answer is no, even though it should be yes.

1.\overline{0}=.\overline{9}

even though

0\ne 9

7.

Problem: Let f:A\to B be a surjective map. Prove that the relation

a\sim b\Leftrightarrow f(a)=f(b)

is an equivalence relation whose equivalence classes are the fibers of f.

Proof: Clearly \sim is reflexive. It’s symmetric just because a\sim b\implies f(a)=f(b)\implies f(b)=f(a)\implies b\sim a. Lastly , it’s transtive because a\sim b,b\sim c implies that f(a)=f(b),f(b)=f(c) and by the transitivity of the equality relation f(a)=f(c) and thus a\sim c. The fact that it’s equivalence classes are the fibers is obvious.

—————————————————————————————————————————–

1.

Problem: For each of the following pairs of integers a and b, determine their greatest common divisor, their least common multiple and write their gcd as a linear combination of the two.

a) a=20,b=13

b) a=69,b=372

c) a=792,b=275

d) a=11391,b=5673

e) a=1761,b=1567

f) a=507885,b=60808

Proof: Omitted. What’s the point really? It’s just manual labor.

2.

Problem: Prove that if the integer k divides the integers a and b then k divides as+bt for every s,t\in\mathbb{Z}

Proof: Since k\mid a,k\mid b this implies that a=z_1k,b=z_2k for some z_1,z_2\in\mathbb{Z}. Thus, as+bt=z_1ks+z_2kt=k\left(z_1s+z_2t\right) and thus k\mid as+bt.

3.

Problem: Prove that if n is composite, then there are integers a and b such that n\mid ab but n\nmid a and n\nmid b

Proof: I assume that we are to not consider 1? Then, this is clearly true since n=ab for some 0<|a|,|b|<n and so n\mid ab=n but n\nmid a,b since 0<|a|,|b|<n

4.

Problem: Let a,b and N be fixed integers with a and b nonzero, and let d=(a,b). Suppose that x_0 and y_0 are particular solutions to ax+by=N. Prove that for any integer t the integers \displaystyle x=x_0+\frac{b}{d}t and \displaystyle y=y_0-\frac{a}{d}t are also solutions to ax+by=N.

Proof: Plugging the numbers into the equation we get

\displaystyle a\left(x_0+\frac{b}{d}t\right)+b\left(y_0-\frac{a}{d}t\right)

which is equa lto

ax_0+by_0+\frac{ab}{d}t-\frac{ba}{d}t=N+0=N

thus, they are all, in fact, solutions.

5.

Problem: Determine the value for \varphi(n) for n=1,\cdots,30

Proof: Omitted. Really? I would just plug these into a calculator.

6.

Problem: Prove the well-ordering property of \mathbb{N} by induction

Proof: Let S be a subset of the natural numbers which has no least element. We claim that S=\varnothing. To see this we first note that by assumption since S has no least element, for each s\in S there is some t\in S such that t<s otherwise s is the least element. So, fix n\in\mathbb{N} and suppose that m\notin S,m=1,\cdots,n-1. Then, clearly n\notin S otherwise there would have to be some m\in\{1,\cdots,n-1\}\cap S  such that m<n (by assumption), but this contradicts that m\notin S,\text{ }m=1,\cdots,n-1. Noting that the base case when there is 1 element in S is clearly true, since if S had one element, clearly that element is minimal.  The conclusion follows.

To prove uniqueness we merely note that if \alpha,\beta=\min\text{ }S then since \beta\in S we have that \alpha\leqslant \beta and since \alpha\in S we have that \beta\leqslant\alpha and so it follows by the anti-symmetry of the \leqslant relation on \mathbb{N} that \alpha=\beta.

7.

Problem: Prove that \sqrt{p}\notin\mathbb{Q} for each prime p.

Proof: Suppose that \displaystyle \sqrt{p}=\frac{m}{n},\text{ }(m,n)=1 then n^2p=m^2. But, clearly this implies that p\mid m^2 which by Euclid’s lemma implies that p\mid m and so m=pm' for some m'\in\mathbb{Z}. Thus, pn^2=p^2m'^2 but this implies that p^2\mid pn^2 and so p\mid n^2 and so by the same lemma p\mid n. But, this implies that p\mid 1 which is a contradiction.

8.

Problem: Let p be a prime, and n\in\mathbb{N}. Find a formula for the largest power of p which divides n!

Proof: For notational convenience let \eta(p,n) be the maximum m such that p^m\mid n. Note that the only numbers divisible by p are of the form pz for some z\in\mathbb{Z}. Thus, there are \displaystyle \left\lfloor \frac{n}{p^1}\right\rfloor=\alpha_1 numbers less than or equal to n which are divisible by p. Thus, there are exactly \alpha_1 factors of n! for which p divides them. Thus, one can think of n! as being written as zp^{\alpha_1} and so we know that \eta(p,n)\geqslant \alpha_1. Note though that every p^2th number is of the form p^2z for some z\in\mathbb{Z} and though one of the p‘s was “counted” by \alpha_1 one wasn’t. Thus, each of these contributes one more to \eta(n,p). Thus, using the same logic \displaystyle \eta(n,p)\geqslant\alpha_1+\alpha_2 where \displaystyle \alpha_2=\left\lfloor \frac{n}{p^2}\right\rfloor. Then, noting that every p^3th number “contributes” three to \eta(n,p) we note that \displaystyle \alpha_1+\alpha_2+\alpha_3 where \displaystyle \alpha_3=\left\lfloor \frac{n}{p^3}\right\rfloor. Continuing on this way and defining \displaystyle \alpha_m=\left\lfloor\frac{n}{p^m}\right\rfloor we may conclude that

\displaystyle \eta(n,p)=\sum_{m=1}^{\infty}\alpha_m

Note that this sum “makes sense” in terms of convergence since for all but finitely many m we have that p^m>n\implies \alpha_m=0.

Remark: This can be proven more rigorously using the Inclusion-Exclusion principle.

9.

Problem: Something with computers! No!

10.

Problem: Prove that for any given N\in\mathbb{N} there exists only finitely many integers n with \varphi(n)=N. Conclude that \varphi(n)\xrightarrow[\quad]{n\to\infty}\infty.

Proof: It is a pretty common fact that for n\ne2,6 we have that \varphi(n)\geqslant \sqrt{n}. The conclusion follows for both parts.

11.

Problem: Prove that if d\mid n then \varphi(d)\mid\varphi(n)

Proof: Let n=p_1^{\alpha_1}\cdots p_m^{\alpha_m}. Then, since d\mid n we have that d=p_{\gamma_1}^{\beta_{\gamma_1}}\cdots p_{\gamma_k}^{\beta_{\gamma_k}} where \{p_{\gamma_1},\cdots,p_{\gamma_k}\}\subseteq\{p_1,\cdots,p_m\} and \beta_{\gamma_\ell}\leqslant \alpha_{\gamma_\ell}. Thus,

\displaystyle \frac{\varphi(n)}{\varphi(d)}=\text{integer}\cdot p_{\gamma_1}^{\alpha_{\gamma_1}-\beta_{\gamma_1}}\frac{p_{\gamma_1}-1}{p_{\gamma_1}-1}\cdots p_{\gamma_k}^{\alpha_{\gamma_k}-\beta_{\gamma_k}}\frac{p_{\gamma_k}-1}{p_{\gamma_k}-1}

where \text{integer} is meant to represent the usual factors in \varphi(n)=p_1^{\alpha_1-1}(p_1-1)\cdots p_m^{\alpha_m-1}(p_m-1) which have no corresponding prime in the representation d=p_{\gamma_1}^{\beta_{\gamma_1}}\cdots p_{\gamma_k}^{\beta_{\gamma_k}}. But, clearly since \alpha_{\gamma_\ell}\geqslant \beta_{\gamma_\ell} we see that \displaystyle \frac{\varphi(n)}{\varphi(d)} is the multiplication of two integers, and thus an integer. The conclusion follows.

———————————————————————————————————————————————————————————–

1.

Problem: Write down explicitly all the elements of the residue classes of \mathbb{Z}/18\mathbb{Z}.

Proof: Why? The idea is that each will look like

\overline{k}=\left\{k+18n:n\in\mathbb{N}\right\}

2.

Problem: Prove that the distinct equivalence classes in \mathbb{Z}/n\mathbb{Z} are \overline{0},\cdots,\overline{n-1}.

Proof: We first note that each of these equivalence classes are distinct, since if \overline{k}\cap\overline{\ell}\ne\varnothing,\text{ }k\ne \ell then we have there is some x\in\overline{k}\cap\overline{\ell}. Thus, by the first membership we have that n\mid x-k and the second membership says that n\mid x-\ell and thus n\mid \ell-k. But, since -(n-1)\leqslant \ell-k\leqslant n-1 this is clearly impossible.

To prove that they are the only distinct equivalence classes we note that if k\in\mathbb{Z} then by the division algorithm says that k=mn+r for some 0\leqslant r\leqslant n-1. Thus, noting that the condition on r implies that r\in\{0,\cdots,n-1\} we note \overline{mn+r}=\overline{r}\in\left\{\overline{0},\cdots,\overline{n-1}\right\}. The conclusion follows.

3.

Problem: Prove that if a=a_0+\cdots+a_n10^n then a\equiv a_0+\cdots+a_n\text{ mod }9.

Proof: This is clear since each a_k10^k\equiv a_k\cdot 1=a_k\text{ mod }9 since 10\equiv 1\text{ mod }9.

4.

Problem: Compute the remainder of 37^{100}\text{ mod }29.

Proof: We first note that since 37\equiv 8\text{ mod }9 that 37^{100}\equiv 8^{100}\text{ mod }9. Thus, noting that (8,29)=1 and \varphi(29)=28 we may appeal to Euler’s theorem to see that

\displaystyle 8^{100}=8^{3\varphi(29)+16}\equiv 8^{16}\text{ mod }29

but

8^{16}=64^8\equiv 6^{8}\text{ mod }29

and

6^8=36^4\equiv 7^4\text{ mod }29

and finally

7^4=49^2\equiv 20^2=400\equiv 23\text{ mod }29

Remark: There is a more clever way to do this introducing the notion of the sum of a geometric sequence in modular arithmetic, but this is slightly more advanced than the book probably wanted.

5.

Problem: Compute the last two digits of 9^{1500}

Proof: Note this is the same as computing 9^{1500}\text{ mod }100. Thus, noting again that (9,100)=1 and \varphi(100)=40 we see that

9^{1500}=9^{37\varphi(100)+20}\equiv 9^{20}\text{ mod }100

Thus, doing again what we did last time we see that

9^{20}=6561^5\equiv 61^5\text{ mod }100

and

61^5=61\times 3721^2\equiv 61\times 21^2=26901\equiv 1\text{ mod }100

6.

Problem: Prove that the squares of the elements of \mathbb{Z}/4\mathbb{Z} are \overline{0},\overline{1}

Proof: \overline{0}^2=\overline{0^2}=\overline{0}, \overline{1}^1=\overline{1^2}=\overline{1}, \overline{2}^2=\overline{2^2}=\overline{4}=\overline{0}, and \overline{3}^2=\overline{3^2}=\overline{9}=\overline{1}.

7.

Problem: Prove that any integers a and b never leave a remainder of three when divided by four.

Proof: By our last problem we have that 0\leqslant a^2+b^2\leqslant 2\text{ mod }4, from where the conclusion follows.

8.

Problem: Prove that the equation a^2+b^2=3c^2 has no solutions in nozero integers a,b and c.

Proof: Note that since (a_0,b_0,c_0) is a solution implies that ( |a_0|,| b_0|,|c_0|) is a solution, it suffices to show there is no solution in \mathbb{N}. Do do this suppose that (a_0,b_0,c_0) is a solution. Then, we have that a_0^2+b_0^2=3c_0^2. Now, we must have that 2\mid c_0 since otherwise we have that c_0\equiv 1,3\text{ mod }4 and so 3c_0^2\equiv 3\text{ mod }4 and thus a_0^2+b_0^2\equiv 3\text{ mod }4, but this is impossible by the last problem. Thus, 2\mid c_0\implies 4\mid c_0^2. So, a_0^2+b_0^2=12d_0^2 for some d_0\in\mathbb{Z}. But, this clearly implies that 2\mid a_0,b_0 and so 4e_0^2+4f_0^2=12d_0^2\implies e_0^2+f_0^2=3d_0^2 and so (e_0,f_0,d_0) is another solution in \mathbb{N} such that e_0<a_0,f_0<b_0,d_0<c_0. But, clearly we may repeat this process ad infinitum to produce infinitely many solutions to a^2+b^2=3c^2 each of which contains numbers strictly less than the previous solution. But, this implies there are infinitely many numbers less than a fixed natural number…which is impossible. It follows that the assumption of an initial solution must have been flawed. The conclusion follows.

9.

Problem: Show that the square of any odd integer always leaves a remainder of 1 when divided by 8

Proof: The only distinct odd residue classes \text{ mod }8 are 1,3,5,7 and so if n is any odd number we have that n^2\equiv 1^2,3^2,5^2,7^2=1,9,24,48\equiv 1\text{ mod }8

10.

Problem: Prove that the number of elements of \left(\mathbb{Z}/n\mathbb{Z}\right)^{\times} is \varphi(n)

Proof: I’m not sure what’s to prove. It was proven in the book that the elements of \left(\mathbb{Z}/n\mathbb{Z}\right)^{\times} are those numbers m such that (m,n)=1. Thus, noting that we must only consider such m with the property that 0\leqslant m\leqslant n-1 we see that there is exactly \varphi(n) of them.

11.

Problem: Prove that \overline{a},\overline{b}\in\left(\mathbb{Z}/n\mathbb{Z}\right)^{\times}\implies \overline{a}\cdot\overline{b}\in\left(\mathbb{Z}/n\mathbb{Z}\right)^{\times}

Proof: By assumption there exists \overline{c},\overline{d}\in\mathbb{Z}_n such that \overline{a}\overline{c}=\overline{b}\overline{d}=\overline{1}. Thus, since \overline{c}\overline{d}\in\mathbb{Z}_n we can see that \overline{a}\overline{b}\overline{c}\overline{d}=\overline{a}\overline{c}\overline{b}\overline{d}\overline{1}\overline{1}=\overline{1} and so \overline{a}\overline{b}\in\left(\mathbb{Z}/n\mathbb{Z}\right)^{\times}

12.

Problem: Let n\in\mathbb{Z} and n>1, and let a\in\mathbb{Z} with 1\leqslant a\leqslant n. Prove if a and n are no relatively prime there exists an integer b with 1\leqslant b< n such that ab\equiv 0\text{ mod }n and thus deduce there is no c\in\mathbb{Z} such that ac\equiv 1\text{ mod }n

Proof: Let d=(a,n)>1. Note then that \displaystyle \frac{a}{d}\in\mathbb{Z} and \displaystyle 1\leqslant \frac{a}{d}<n. Also, note that \displaystyle a\cdot\frac{n}{d}=\frac{a}{d}\cdot n=mn\equiv 0\text{ mod }n, the important part noting that \displaystyle \frac{a}{d}=m\in\mathbb{Z}. This proves the second part by letting \displaystyle b=\frac{a}{d}

Now, clearly we can’t have that ac\equiv 1\text{ mod }n otherwise we’d have that b\equiv b(ac)=(ba)c\equiv 0\cdot c=0\text{ mod }n which is preposterous.

13.

Problem: Let n\in\mathbb{Z},n>1 and let a\in\mathbb{Z} with 1\leqslant a\leqslant n. Prove that if (a,n)=1 then there is an integer c such that ac\equiv 1\text{ mod }n.

Proof: This follows immediately since ax+bn=1 has a solution for x,y\in\mathbb{Z}.

14.

Problem: Conclude from the previous two exercises that \left(\mathbb{Z}/n\mathbb{Z}\right)^{\times} is the set of elements \overline{a}\in\mathbb{Z}/n\mathbb{Z} with (a,n)=1.

Proof: If R(n)=\left\{\overline{a}:(a,n)=1\right\} the first exercise shows that \left(\mathbb{Z}/n\mathbb{Z}\right)^{\times}\subseteq R(n) and the second shows that R(n)\subseteq\left(\mathbb{Z}/n\mathbb{Z}\right)^{\times}.

We choose to omit 15 and 16 being computational and computer related.

Advertisements

June 14, 2010 - Posted by | Algebra, Fun Problems, Uncategorized | , , , , , , ,

1 Comment »

  1. Hi Drexel,
    Nice blog! You should make PDFs with your solutions.
    I’d just like to suggest different solutions to 2.11 and to 3.8.

    2.11 : let f : (Z/nZ)^* –> (Z/dZ)^* be reduction mod d. This is a surjective homomorphism, so phi(d) | phi(n).

    3.8 : We can suppose gcd(a,b,c)=1. Now reduce both sides mod 4; the only possibility is that a,b,c all be even, which contradicts the assumption!

    Comment by Bruno | June 19, 2010 | Reply


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: