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

In exercises 1 to 4 let be the set of all matrices with real number entries. Recall that matrix multiplication is defined by

Let

and

**1.**

**Problem: **Determine which of the following matrices lie in

**a) **

**b) **

**c) **

**d) **

**e) ** (the identity)

**f) **

**Solution:**

**a) **Clearly since

**b) **No.

**c) **Clearly this will commute with .

**d) **Doesn’t commute.

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

**f) **Doesn’t commute.

**2.**

**Problem:** Prove that if then

**Proof:** Note that

The conclusion follows.

**3.**

**Problem:** Prove that if then

**Proof: **Merely note that

from where the conclusion follows.

**4.**

**Problem: **Find the conditions on which determine when

**Proof:** A simple calculations shows that

And since evidently

It follows that

**5.**

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

**a) **

**b) **

**Proof:**

**a) **Clearly this is not well defined since

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

**6.**

**Problem: **Determine whether the function 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.

even though

**7.**

**Problem:** Let be a surjective map. Prove that the relation

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

**Proof:** Clearly is reflexive. It’s symmetric just because . Lastly , it’s transtive because implies that and by the transitivity of the equality relation and thus . The fact that it’s equivalence classes are the fibers is obvious.

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

**1.**

**Problem: **For each of the following pairs of integers and , 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 divides the integers and then divides for every

**Proof:** Since this implies that for some . Thus, and thus .

**3.**

**Problem: **Prove that if is composite, then there are integers and such that but and

**Proof:** I assume that we are to not consider ? Then, this is clearly true since for some and so but since

**4.**

**Problem: **Let and be fixed integers with and nonzero, and let . Suppose that and are particular solutions to . Prove that for any integer the integers and are also solutions to .

**Proof:** Plugging the numbers into the equation we get

which is equa lto

thus, they are all, in fact, solutions.

**5.**

**Problem:** Determine the value for for

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

**6.**

**Problem:** Prove the well-ordering property of by induction

**Proof:** Let be a subset of the natural numbers which has no least element. We claim that . To see this we first note that by assumption since has no least element, for each there is some such that otherwise is the least element. So, fix and suppose that . Then, clearly otherwise there would have to be some such that (by assumption), but this contradicts that . Noting that the base case when there is element in is clearly true, since if had one element, clearly that element is minimal. The conclusion follows.

To prove uniqueness we merely note that if then since we have that and since we have that and so it follows by the anti-symmetry of the relation on that .

**7.**

**Problem:** Prove that for each prime .

**Proof: **Suppose that then . But, clearly this implies that which by Euclid’s lemma implies that and so for some . Thus, but this implies that and so and so by the same lemma . But, this implies that which is a contradiction.

**8.**

**Problem: **Let be a prime, and . Find a formula for the largest power of which divides

**Proof: **For notational convenience let be the maximum such that . Note that the only numbers divisible by are of the form for some . Thus, there are numbers less than or equal to which are divisible by . Thus, there are exactly factors of for which divides them. Thus, one can think of as being written as and so we know that . Note though that every th number is of the form for some and though one of the ‘s was “counted” by one wasn’t. Thus, each of these contributes one more to . Thus, using the same logic where . Then, noting that every th number “contributes” three to we note that where . Continuing on this way and defining we may conclude that

Note that this sum “makes sense” in terms of convergence since for all but finitely many we have that .

*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 there exists only finitely many integers with . Conclude that .

**Proof:** It is a pretty common fact that for we have that . The conclusion follows for both parts.

**11.**

**Problem: **Prove that if then

**Proof:** Let . Then, since we have that where and . Thus,

where is meant to represent the usual factors in which have no corresponding prime in the representation . But, clearly since we see that 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 .

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

**2. **

**Problem**: Prove that the distinct equivalence classes in are .

**Proof: **We first note that each of these equivalence classes are distinct, since if then we have there is some . Thus, by the first membership we have that and the second membership says that and thus . But, since this is clearly impossible.

To prove that they are the only distinct equivalence classes we note that if then by the division algorithm says that for some . Thus, noting that the condition on implies that we note . The conclusion follows.

**3.**

**Problem: **Prove that if then .

**Proof: **This is clear since each since .

**4.**

**Problem: **Compute the remainder of .

**Proof:** We first note that since that . Thus, noting that and we may appeal to Euler’s theorem to see that

but

and

and finally

*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

**Proof:** Note this is the same as computing . Thus, noting again that and we see that

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

and

**6.**

**Problem: **Prove that the squares of the elements of are

**Proof: **, , , and .

**7.**

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

**Proof:** By our last problem we have that , from where the conclusion follows.

**8.**

**Problem: **Prove that the equation has no solutions in nozero integers and .

**Proof:** Note that since is a solution implies that is a solution, it suffices to show there is no solution in . Do do this suppose that is a solution. Then, we have that . Now, we must have that since otherwise we have that and so and thus , but this is impossible by the last problem. Thus, . So, for some . But, this clearly implies that and so and so is another solution in such that . But, clearly we may repeat this process ad infinitum to produce infinitely many solutions to 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 are and so if is any odd number we have that

**10.**

**Problem: **Prove that the number of elements of is

**Proof:** I’m not sure what’s to prove. It was proven in the book that the elements of are those numbers such that . Thus, noting that we must only consider such with the property that we see that there is exactly of them.

**11.**

**Problem: **Prove that

**Proof:** By assumption there exists such that . Thus, since we can see that and so

**12.**

**Problem: **Let and , and let with . Prove if and are no relatively prime there exists an integer with such that and thus deduce there is no such that

**Proof:** Let . Note then that and . Also, note that , the important part noting that . This proves the second part by letting

Now, clearly we can’t have that otherwise we’d have that which is preposterous.

**13.**

**Problem: **Let and let with . Prove that if then there is an integer such that .

**Proof:** This follows immediately since has a solution for .

**14.**

**Problem: **Conclude from the previous two exercises that is the set of elements with .

**Proof:** If the first exercise shows that and the second shows that .

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

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 |