Hints, Solutions and Help -- a companion to GIAM

Chapter 1 -- Introduction and notation

Section 1.1 -- Basic sets

  1. Each of the quantities indexing the rows of the following table is in one or more of the sets which index the columns. Place a check mark in a table entry if the quantity is in the set.
      N  Z  Q  R  C 
    17     
    $\pi$     
    22/7     
    -6     
    e0     
    1+i     
    $\sqrt{3}$     
    i2     

    Note that these sets contain one another, so if you determine that a number is a natural number it is automatically an integer and a rational number and a real number and a complex number...
  2. Write the set $\mathbb Z$ of integers using a singly infinite listing.

    What the heck is meant by a "singly infinite listing "? To help you figure this out, note that

    ... -3, -2, -1, 0, 1, 2, 3, ...

    is a doubly infinite listing.

  3. Give a description of the set of rational numbers whose decimal expansions terminate. (Alternatively, you may think of their decimal expansions ending in an infinitely-long string of zeros.)

    If a decimal expansion terminates after, say, k digits, can you figure out how to produce an integer from that number? Think about multiplying by something...
  4. Find the first 20 decimal places of $\pi$, 3/7, $\sqrt{2}$, 2/5, 16/17, $\sqrt{3}$, 1/2 and 42/100. Classify each of these quantity's decimal expansion as: terminating, having a repeating pattern, or showing no discernible pattern.

    A calculator will generally be inadequate for this problem. You should try using a CAS (Computer Algebra System). In the computer labs at SCSU you have access to Maple, a CAS from a Canadian company called Waterloo Maple. Try searching Maple's help facility for the variable DIGITS.
  5. Consider the process of long division. Does this algorithm give any insight as to why rational numbers have terminating or repeating decimal expansions? Explain.

    You really need to actually sit down and do some long division problems. When in the process do you suddenly realize that the digits are going to repeat? Must this decision point always occur? Why?
  6. Give an argument as to why the product of two rational numbers is again a rational.

    Take for granted that the usual rule for multiplying two fractions is okay to use:

    (a/b)*(c/d) = (ac)/(bd).

    How do you know that the result is actually a rational number?

  7. Perform the following computations with complex numbers
    1. (4 + 3i) - (3 + 2i)
    2. (1 + i) + (1 - i)
    3. (1 + i) · (1 - i)
    4. (2 - 3i) · (3 - 2i)

    These are straightforward. If you really must verify these somehow, you can go to a CAS or you can learn how to enter complex numbers on your graphing calculator. (On my TI-84, you get i by hitting the 2nd key and then the decimal point.)
  8. The conjugate of a complex number is denoted with a superscript star, and is formed by negating the imaginary part. Thus if z = 3 + 4i then the conjugate of z is z* = 3 - 4i. Give an argument as to why the product of a complex number and its conjugate is a real quantity. (I.e. the imaginary part of the product of z and z* is necessarily 0, no matter what complex number is used for z.)

    This is really easy, but be sure to do it generically. In other words, don't just use examples -- do the calculation with variables for the real and imaginary parts of the complex number.

Section 1.2 -- Definitions: Prime numbers

  1. Find the prime factorizations of the following integers.
    1. 105
    2. 414
    3. 168
    4. 1612

    Divide out the obvious factors in order to reduce the complexity of the remaining problem. The first number is divisible by 5. The last three are all even. Recall that a number is divisible by 3 if and only if the sum of its digits is divisible by 3.
  2. Use the sieve of Eratosthenes to find all prime numbers up to 100.
     1  2  3  4  5  6  7  8  9  10 
     11  12  13  14  15  16  17  18  19  20 
     21  22  23  24  25  26  27  28  29  30 
     31  32  33  34  35  36  37  38  39  40 
     41  42  43  44  45  46  47  48  49  50 
     51  52  53  54  55  56  57  58  59  60 
     61  62  63  64  65  66  67  68  69  70 
     71  72  73  74  75  76  77  78  79  80 
     81  82  83  84  85  86  87  88  89  90 
     91  92  93  94  95  96  97  98  99  100 

    The primes used in this instance of the sieve are just 2, 3, 5 and 7. Any number less than 100 that isn't a multiple of 2, 3, 5 or 7 will not be crossed off during the sieving process. If you're still unclear about the process, try a web search for "Sieve of Eratosthenes" +applet, there are several interactive applets that will help you to understand how to sieve.
  3. What would be the largest prime one would sieve with in order to find all primes up to 400?

    Remember that if a number factors into two multiplicands, the smaller of them will be less than the square root of the original number.
  4. Complete the following table which is related to Conjecture 1.
    p    2p-1    prime?    factors
    2    3    yes    1 and 3
    3    7    yes    1 and 7
    5    31    yes   
    7    127      
    11         

    You'll need to determine if 211-1 = 2047 is prime or not. If you never figured out how to read the table of primes on page 15, here's a hint: If 2047 was a prime there would be a 7 in the cell at row 20, column 4.

    A quick way to find the factors of a not-too-large number is to use the "table" feature of your graphing calculator. If you enter y1=2047/X and select the table view (2ND GRAPH). Now, just scan down the entries until you find one with nothing after the decimal point. That's an X that evenly divides 2047!

  5. Characterize the prime factorizations of numbers that are perfect squares.

    It might be helpful to write down a bunch of examples. Think about how the prime factorization of a number gets transformed when we square it.
  6. Find a counterexample for Conjecture 2.

    Part of what makes the "prime-producing-power" of that polynomial impressive is that it gives each prime twice -- once on the descending arm of the parabola and once on the ascending arm. In other words, the polynomial gives prime values on a set of contiguous natural numbers {0,1,2, ..., N} and the vertex of the parabola that is its graph lies dead in the middle of that range. You can figure out what N is by thinking about the other end of the range: (-1)2 + 31 · (-1) + 257 = 289 (289 is not a prime, you should recognize it as a perfect square.)
  7. Use the second definition of "prime" to see that 6 is not a prime. In other words, find two numbers (the a and b that appear in the definition) such that 6 is not a factor of either, but is a factor of their product.

    Well, we know that 6 really isn't a prime... Maybe its factors enter into this somehow...
  8. A famous conjecture that is thought to be true (but for which no proof is known) is the Twin Prime conjecture. A pair of primes is said to be twin if they differ by 2. For example, 11 and 13 are twin primes, as are 431 and 433. The Twin Prime conjecture states that there are an infinite number of such twins. Try to come up with an argument as to why 3, 5 and 7 are the only prime triplets.

    It has to do with one of the numbers being divisible by 3. (Why is this forced to be the case?) If that number isn't actually 3, then you know it's composite.
  9. Another famous conjecture, also thought to be true -- but as yet unproved, is Goldbach's conjecture. Goldbach's conjecture states that every even number greater than 4 is the sum of two odd primes. There is a function g(n), known as the Goldbach function, defined on the positive even integers, that gives the number of different ways to write a given even number as the sum of two odd primes. For example g(10) = 2 since 10=5+5=7+3. Thus another version of Goldbach's conjecture is that g(n) is positive whenever n is an even number greater than 4. Graph g(n) for 6 <= n <= 20.

    If you don't like making graphs, a table of the values of g(n) would suffice. Note that we don't count sums twice that only differ by order. For example, 16 = 13+3 and 11+5 (and 5+11 and 3+13) but g(16)=2.

Section 1.3 -- More scary notation

  1. How many quantifiers (and what sorts) are in the following sentence? "Everybody has some friend that thinks they know everything about some sport."

    Well, I'll give you that there are four.
  2. The sentence "Every metallic element is a solid at room temperature." is false. Why?

    The chemical symbol for the element that is the exception is Hg which stands for "Hydro-argyrum" it is also known as "liquid silver" or "quick silver".
  3. The sentence "For every pair of (distinct) real numbers there is another real number between them." is true. Why?

    Think about this: is there any way to (using a formula) find a number that lies in between two other numbers?
  4. Write your own sentences containing four quantifiers. One sentence in which the quantifiers appear (forall exists forall exists) and another in which they appear (exists forall exists forall).

    You're on your own here. Be inventive!

Section 1.4 -- Definitions of elementary number theory

  1. An integer n is doubly-even if it is even, and the integer m guaranteed to exist because n is even is itself even. Is 0 doubly-even? What are the first 3 positive, doubly-even integers?

    Yes. 0, 4 and 8.
  2. Dividing an integer by two has an interesting interpretation when using binary notation: simply shift the digits to the right. Thus, 22 = 101102 when divided by two gives 10112 which is 8+2+1=11. How can you recognize a doubly-even integer from its binary representation?

    Even numbers have a zero in their units place. What digit must also be zero in a doubly-even number's binary representation?
  3. The octal representation of an integer uses powers of 8 in place notation. The digits of an octal number run from 0 to 7, one never sees 8's or 9's. How would you represent 8 and 9 as octal numbers? What octal number comes immediately after 7778? What (decimal) number is 7778?

    Eight is 108, nine is 118. The point of asking questions about 777, is that (in octal) 7 is the digit that is analogous to 9 in base-10. Thus 7778 is something like 99910 in that the number following both of them is written 1000 (although 10008 and 100010 are certainly not equal!)
  4. One method of converting from decimal to some other base is called repeated division. One divides the number by the base and records the remainder -- one then divides the quotient obtained by the base and records the remainder. Continue dividing the successive quotients by the base until the quotient is smaller than the base. Convert 3267 to base-7 using repeated division. Check your answer by using the meaning of base-7 place notation. (For example 543217 means 5·74 + 4·73 + 3 ·72 + 2·71 + 1·70.)

    It is helpful to write something of the form n = qd+r at each stage. The first two stages should look like

    3267 = 466·7 + 5

    466 = 66·7 + 4

    you do the rest...

  5. State a theorem about the octal representation of even numbers.

    One possibility is to mimic the result for base-10 that an even number always ends in 0,2,4,6 or 8.
  6. In hexadecimal (base-16) notation one needs 16 "digits," the ordinary digits are used for 0 through 9, and the letters A through F are used to give single symbols for 10 through 15. The first 32 natural number in hexadecimal are: 1,2,3,4,5,6,7,8,9,A,B,C,D,E,F,10,11,12,13,14,15,16,17,18,19,1A, 1B,1C,1D,1E,1F,20. Write the next 10 hexadecimal numbers after AB. Write the next 10 hexadecimal numbers after FA.

    As a check, the tenth number after AB is B5.
    The tenth hexadecimal number after FA is 104.
  7. For conversion between the three bases used most often in Computer Science we can take binary as the "standard" base and convert using a table look-up. Each octal digit will correspond to a binary triple, and each hexadecimal digit will correspond to a 4-tuple of binary numbers. Complete the following tables. (As a check, the 4-tuple next to A in the table for hexadecimal should be 1010 -- which is nice since A is really 10 so if you read that as "ten-ten" it is a good aid to memory.)
     
      octal     binary  
      0    000
      1    001
      2   
      3   
      4   
      5   
      6   
      7   
         		     
      hexadecimal    binary  
      0    0000
      1    0001
      2    0010
      3   
      4   
      5   
      6   
      7   
      8   
      9   
      A   
      B   
      C   
      D   
      E   
      F   

    This is just counting in binary. Remember the sanity check that the hexadecimal digit A is represented by 1010 in binary. (1010 = A16 =10102)
  8. Use the tables above to make the following conversions.
    1. Convert 7578 to binary.
    2. Convert 10078 to hexadecimal.
    3. Convert 1001010101102 to octal.
    4. Convert 1111101000110101 to hexadecimal.
    5. Convert FEED16 to binary.
    6. Convert FFFFFF16 to octal.

    Answers for the first three:
    7578 = 111 101 1112
    10078 = 001 000 000 1112 = 0010 0000 01112 = 20716
    100 101 010 1102 = 45268
  9. It is a well known fact that if a number is divisible by 3, then 3 divides the sum of the (decimal) digits of that number. Is this result true in base 7? Do you think this result is true in any base?

    Might this effect have something to do with 10 being just one bigger than 9 (a multiple of 3)?
  10. Suppose that 340 pounds of sand must be placed into bags having a 50 pound capacity. Write an expression using either floor or ceiling notation for the number of bags required.

    Seven 50 pound bags would hold 350 pounds of sand. They'd also be able to handle 340 pounds!
  11. Assuming the symbols n,d,q and r have meanings as in the quotient-remainder theorem. Write expressions for q and r, in terms of n and d using floor and/or ceiling notation.

    I can't spoil this one for you, you really need to work this one out on your own.
  12. Calculate the following quantities:
    1. 3 mod 5
    2. 37 mod 7
    3. 1000001 mod 100000
    4. 6 div 6
    5. 7 div 6
    6. 1000001 div 2

    The even numbered ones are 2, 1, 500000.
  13. Calculate the following binomial coefficients:
    1. C(3,0)
    2. C(7,7)
    3. C(13,5)
    4. C(13,8)
    5. C(52,7)

    The even numbered ones are 1 and 1287. The TI-84 calculates binomial coefficients. The symbol used is nCr (which is placed between the numbers -- i.e. it is an infix operator). You get nCr as the 3rd item in the PRB menu under MATH.
  14. An ice cream shop sells the following flavors: chocolate, vanilla, strawberry, coffee, butter pecan, mint chocolate chip and raspberry. How many different bowls of ice cream -- with three scoops -- can they make?

    You're choosing three things out of a set of size seven...

Section 1.5 -- Some algorithms of elementary number theory

  1. Trace through the division algorithm with inputs n=27 and d=5, each time an assignment statement is encountered write it out. How many assignments are involved in this particular computation?

    r=27
    q=0
    r=27-5=22
    q=0+1=1
    r=22-5=17
    q=1+1=2
    r=17-5=12
    q=2+1=3
    r=12-5=7
    q=3+1=4
    r=7-5=2
    q=4+1=5
    return r is 2 and q is 5.
  2. Find the gcd's and lcm's of the following pairs of numbers.
    a    b    gcd(a,b)    lcm(a,b)
    110    273      
    105    42      
    168    189      

    For such small numbers you can just find their prime factorizations and use that, although it might be useful to practice your understanding of the Euclidean algorithm by tracing through it to find the gcd's and then using the formula

    lcm(a,b) = ab/gcd(a,b).

  3. Formulate a description of the gcd of two numbers in terms of their prime factorizations in the general case (when the factorizations may include powers of the primes involved).

    Suppose that one number's prime factorization contains pe and the other contains pf, where e < f. What power of p will divide both, pe or pf ?
  4. Trace through the Euclidean algorithm with inputs a=3731 and b=2730, each time the assignment statement that calls the division algorithm is encountered write out the expression a=qb+r. (With the actual values involved !)

    You're on you own here.

Section 1.6 -- Rational and irrational numbers

  1. Rational Approximation is a field of mathematics that has received much study. The main idea is to find rational numbers that are very good approximations to given irrationals. For example, 22/7 is a well-known rational approximation to $\pi$. Find good rational approximations to $\sqrt{2}$, $\sqrt{3}$, $\sqrt{5}$ and e.

    One approach is to truncate a decimal approximation and then rationalize. E.g. $\sqrt{2}$ is approximately 1.4142, so 14142/10000 isn't a bad approximator (although naturally 7071/5000 is better since it involves smaller numbers).
  2. The theory of base-n notation that we looked at in sub-section 1.4.2 can be extended to deal with real and rational numbers by introducing a decimal point (which should probably be re-named in accordance with the base) and adding digits to the left of it. For instance 1.1011 is binary notation for 1 · 20 + 1 · 2-1 + 0 · 2-2 + 1· 2-3 + 1· 2-4 or 1 + 1/2 + 1/8 + 1/16 = 1 11/16. Consider the binary number .1010010001000010000010000001..., is this number rational or irrational? Why?

    Does the rule about rational numbers having terminating or repeating decimal representations carry over to other bases?
  3. If a number x is even, it's easy to show that its square x2 is even. The lemma that went unproved in this section asks us to start with a square (x2) that is even and deduce that the UN-squared number (x) is even. Perform some numerical experimentation to check whether this assertion is reasonable. Can you give an argument that would prove it?

    What if the lemma wasn't true? Can you work out what it would mean if we had a number x such that x2 was even but x itself was odd?
  4. The proof that $\sqrt{2}$ is irrational can be generalized to show that $\sqrt{p}$ is irrational for every prime number p. What statement would be equivalent to the lemma about the parity of x and x2 in such a generalization?

    Hint: Saying "x is even" is the same thing as saying "x is evenly divisible by 2". Replace the 2 by p and you're halfway there...
  5. Write a proof that $\sqrt{3}$ is irrational.

    Yeah, do that!

Section 1.7 -- Relations

  1. Consider the numbers from 1 to 10. Give the set of pairs of these numbers that corresponds to the divisibility relation.

    A pair is "in" the relation when the first number gazinta the second number. 1 gazinta anything, 2 gazinta the even numbers, 3 gazinta 3, 6 and 9, etc. (Also a number always gazinta itself.)
  2. The domain of a function (or binary relation) is the set of numbers appearing in the first coordinate. The range of a function (or binary relation) is the set of numbers appearing in the second coordinate. Consider the set {0,1,2,3,4,5,6} and the function f(x) = x2 (mod 7). Express this function as a relation by explicitly writing out the set of ordered pairs it contains. What is the range of this function?

    {(0,0), (1,1), (2,4), (3,2), (4,2), (5,4), (6,1)}
    {0,1,2,4}
  3. What relation on the numbers from 1 to 10 does the following set of ordered pairs represent?
      (1,1)   (1,2)   (1,3)   (1,4)   (1,5)   (1,6)   (1,7)   (1,8)   (1,9)   (1,10) 
     (2,2)   (2,3)   (2,4)   (2,5)   (2,6)   (2,7)   (2,8)   (2,9)   (2,10) 
     (3,3)   (3,4)   (3,5)   (3,6)   (3,7)   (3,8)   (3,9)   (3,10) 
     (4,4)   (4,5)   (4,6)   (4,7)   (4,8)   (4,9)   (4,10) 
     (5,5)   (5,6)   (5,7)   (5,8)   (5,9)   (5,10)  
     (6,6)   (6,7)   (6,8)   (6,9)   (6,10)  
     (7,7)   (7,8)   (7,9)   (7,10)  
     (8,8)   (8,9)   (8,10)  
     (9,9)   (9,10)  
     (10,10)

    I'd say it's less-than-or-equal-to.
  4. Draw a five-pointed star, label all 10 points. There are 40 triples of these labels that satisfy the betweenness relation. List them.

    Yeah, hmmm. Forty is kind of a lot...

    Let's look at the points (E,F,G and B) on the horizontal line in the diagram below. The triples involving these four points are: (E,F,G), (G,F,E), (E,F,B), (B,F,E), (E,G,B), (B,G,E), (F,G,B), (B,G,F).

  5. A function f(x) is said to be invertible if there is another function g(x) such that g(f(x)) = x for all values of x. (Usually, the inverse function, g(x) would be denoted f-1(x).) Suppose a function is presented to you as a relation -- that is, you are just given a set of pairs. How can you distinguish whether the function represented by this list of input/output pairs is invertible? How can you produce the inverse (as a set of ordered pairs)?

    If f sends x to y, then we want f-1 to send y back to x. So the inverse just has the pairs in f reversed. When is the inverse going to fail to be a function?