Processing math: 100%
     

Exercises - The Fundamental Theorem of Arithmetic

  1. Suppose we call numbers of the form a+b10 (where a and b are integers) extended integers.

    1. Prove that the extended integers behave much like the integers themselves, in that they are

      1. ... closed under addition.
      2. ... closed under subtraction.
      3. ... closed under multiplication.
      4. ... not closed under division.

       
      1. We need to show that the sum of two extended integers is also an extended integer. That is to say, the sum of two numbers of the form a+b10 (where a and b are integers) is of the same form. So consider two such extended integers, say a1+b110 and a2+b210, and their sum: (a1+b110)+(a2+b210)=(a1+a2)+(b1+b2)10 Upon noting that a1+a2 and b1+b2 are integers by closure, we are done.

      2. We need to show that the difference of two extended integers is also an extended integer. That is to say, the difference of two numbers of the form a+b10 (where a and b are integers) is of the same form. So consider two such extended integers, say a1+b110 and a2+b210, and their difference: (a1+b110)(a2+b210)=(a1a2)+(b1b2)10 Upon noting that a1a2 and b1b2 are integers by closure, we are done.

      3. We need to show that the product of two extended integers is also an extended integer. That is to say, the product of two numbers of the form a+b10 (where a and b are integers) is of the same form. So consider two such extended integers, say a1+b110 and a2+b210, and their product: (a1+b110)(a2+b210)=a1a2+a1b210+b1a210+10b1b2=(a1a2+10b1b2)+(a1b2+b1a2)10 Upon noting that (a1a2+10b1b2) and (a1b2+b1a2) are integers by closure, we are done.

      4. We need to show that the quotient of two extended integers need not be an extended integer. That is to say, the quotient of two numbers of the form a+b10 (where a and b are integers) does not need to be of the same form. Finding one explicit counterexample will suffice. So consider the two extended integers 4+10 and 410, and their quotient: 4+10410=4+104104+104+10=16+810+101610=26+8106=266+8106=133+4310 It should be clear, given this last expression, if we force things into a+b10 form, we are required to have a and b not be integers. We have then found a quotient of two extended integers, which was not an extended integer itself. As such, extended integers are not closed under division.

    2. Both 1 and 1 divide every integer. We call these numbers units. In the set of integers, there are only these two values which are units -- but what about the extended integers? Prove that 3+10 is a unit for the extended integers. What characteristic must units of extended integers have?

      Hint: when one divides an extended integer by a unit, and tries to write it as an extended integer (possibly involving a multiplication by a conjugate), what must be true of the resulting denominator to be assured the coefficient on 10 turns out to be an integer?

       

      Let a+b10 be any extended integer, and then consider the quotient:

      a+b103+10=(a+b10)(310)(3+10)(310)=(3a10b)+(3ba)10)1=(3a10b1)+(3ba1)10=(10b3a)+(a3b)10

      As a and b are integers, (10b3a) and (a3b) are integers as well (by closure). Consequently, (10b3a)+(a3b)10 is an extended integer.

      We have thus shown that the quotient of any extended integer and 3+10 must also be an extended integer. Hence, 3+10 "divides" every extended integer -- making it a unit.

      Notice, looking at what transpired in the denominators above, the key value that determines whether or not a given extended integer is a unit is the product of that extended integer and its conjugate. If this product is 1 or 1 (the only values that can evenly divide every integer), then the extended integer in question is a unit -- otherwise it is not.

    3. In the set of integers, one can define the primes to be those integers that can't be written as the product of two non-units. One might wonder which numbers in the set of extended integers have this same property. Prove that 2, 3, and 4±10 are all extended integers that can't be written as the product of two non-units.

      Hint: argue indirectly -- assume they can be written as the product of two non-units and attempt to show that no matter what happens, one of the factors ends up having the defining characteristic of units found above. To do this, try to put things back into the realm of integers by considering the product of the extended integers in question and their conjugates:
      m+n10=(a+b10)(c+d10), thenmn10=(ab10)(cd10), and som210n2=(a210b2)(c210d2)

      Now we can think about the possible factorizations of m210n2 over the integers, as m and n are chosen so that m+n10 yields 2,3,4+10 and 410, respectively.

      Use these factorizations to show if a+b10 and c+d10 are not units (remember the condition you found in problem 2 above), then in each of these four cases:
      a210b2andc210d2
      must be 2,2,3, or 3. Finally, show that for any a,
      a20,1, or 4(mod5) and therefore,
      a210b2=2,2,3, or 3
      has no integral solutions.

       

      We need to show that if 4+10 can be written as a product of two extended integers, then one of those extended integers must be a unit.

      As such, suppose we can find extended integers a+b10 and c+d10 such that

      4+10=(a+b10)(c+d10)

      Consider the conjugate of 4+10. Clearly if the above is true, we also know that

      410=(ab10)(cd10)

      Taken together, we can then conclude

      (4+10)(410)=(a+b10)(c+d10)(ab10)(cd10)

      This is advantageous as the left side can be collapsed into an integer, and the right side (upon combining the appropriate conjugate pairs with one another) can be collapsed to the product of two integers...

      6=(a210b2)(c210d2)

      Now we know that the only integer divisors 6 has are: ±1,±2,±3, and ±6. We deal with each case separately:

      • If a210b2=±1, then a+b10 was a unit, and we are done.

      • If a210b2=±6, then c210d2=±1. This makes c+d10 a unit, and we are again done.

      • The last two possibilities actually lead to a contradiction and consequently can't happen. To see this, consider the following:

        If a210b2=±2 or a210b2=±3, then remainder of a210b2 upon division by 5 must either be 2 or 3. Further, since 10b2 is a multiple of 5, we can conclude that a2 itself, upon division by 5, must either leave remainder 2 or 3.

        However, if a has remainder 0 upon division by 5, a2 does as well; if a has remainder 1 or 4, then a2 has remainder 1; and if a has remainder 2 or 3, then a2 has remainder 4. Since these are the only possibilities for the remainders of a, it must be the case that a2 never has remainder 2 or 3 upon division by 5. This gives us the desired contradiction.

      Hence, the extended integer 4+10 can't be written as the product of two non-units.

      Note: showing that the extended integers 2, 3, and 410 also can't be written as the product of two non-units is done in a nearly identical way -- except there are fewer cases to worry about with regard to the divisors of a210b2, as argued above, when looking at 2 and 3.

    4. Suppose we call extended integers that can't be written as the product of two non-units indivisibles. Certainly, 6 can be written as the product of two indivisibles, as 6=23. Can you find two different indivisibles m and n, such that 6=mn?

      We know that 2 is prime and 26. Does 2 have to divide either m or n? What might you conclude about the statement "if p is prime and pmn, then pm or pn" and the unique factorization of integers?

       

      Note: 6=(4+10)(410), a product of two indivisibles.

      Taking a step back, notice that extended integers and indivisibles are very closely related to the integers and primes, and yet even though we seem to have unique factorization into primes for integers (up to the order and signs of the factors), we don't have unique factorization into indivisibles for the extended integers.

      Further, even though it seems obvious that if p is prime with pmn, then pm or pn is true for the integers, the same can't be said for some indivisible p with respect to the extended integers. As an example, consider 2(4+10)(410).

      Clearly, there is more to this innocent-looking implication and the idea of unique factorization than first appears!

  2. Prove that log57 is irrational.  

    Argue indirectly. Assume x=log57 is rational. Thus, there exist non-zero integer values p and q where p/q=log57. This implies 5p/q=7, and thus 5p=7q. Both 5 and 7 are prime, however, so this violates the unique factorization property of the integers. We have the contradiction we sought. Thus, log57 must be irrational.

  3. Prove that every root of an equation of the form xn+cn1xn1+cn2xn2++c1x+c0=0 (with each ciZ) is either an integer or irrational, and then use this to show 317, 511, and 1113 are all irrational.

    Hint: argue the main result indirectly. Assume there is a rational root (i.e., a root expressable as a fraction of integers in lowest terms a/b) and try to contradict the lowest terms nature of the fraction in question.

  4. Prime numbers are defined as those numbers that have exactly two divisors. What type of numbers have exactly three divisors? ...exactly four divisors?

  5. Prove that every integer n1 can be written as a product of an integer squared and an integer that has no divisors that are perfect squares (i.e., a square-free integer).