SOAR Homework Four

These homework problems are meant to expand your understanding of what goes on during class. Any you turn in will be graded and returned to you. Answers may or may not be posted on the web, depending on demand.

Problems

  1. What is the last digit of 7213? This sort of question is common in contests. This problem walks you through answering this question.
    1. What we're asked for is 7213 mod 10. Make a table with the values, modulo 10, of 71 = 7, 72, 74, 78, 716, 732, 764, and 7128. (We don't need 7256 as 213 < 256.)

    2. Write 213 as a sum of numbers from the set {1, 2, 4, 8, 16, 32, 64, 128}.

    3. Write 7213 as a product of numbers from the set {71, 72, 74, 78, 716, 732, 764, 7128}.

    4. Use your table from part (a) to compute 7213 modulo 10.

  2. Follow the process of the previous problem to find the last digit of the following numbers.
    1. 3521

    2. M4253 = 24253-1 (This is the 19th Mersenne prime, which are prime numbers of the form Mp = 2p - 1.)

    3. F5 = 225 + 1. (This is the first Fermat number that is not prime. Fermat numbers are those of the form Fn = 22n+1.)

  3. We could apply the same procedures from the previous two problems to other bases other than 10. Commonly used bases are 2 (binary), 8 (octal), 12 (``clock''), and 16 (hexadecimal, where A is used for 10, B for 11, and so on up to F for 15). Thus, for example, 29 base 10 is 1D base 16. On the other hand, 29 º 13 mod 16, so the ``last digit'' when 29 is written in base 16 must be 13 = D.
    1. Find the last digit of 3521 (base 10) when it is written base 8.

    2. Find the last digit of 3521 (base 10) when it is written base 16.

    3. Find the last digit of M4253 and F5 when they are written base 16. (This is easier than it looks at first, and much easier than it was base 10.)

  4. In this problem, we derive a formula for the Euler phi-function (also known as the totient function). Recall that this is defined as
    phi(n) = the number of integers k with 0 < k < n and gcd
    		(k,n) = 1.
    1. Prove that for a prime p, phi(pn) = (p-1) pn-1. (Hint: what are the integers 0 < k < pn that have a common factor with pn?)

    2. (Hard, and I recommend you skip this part and just assume this for part (c).) Prove that phi is multiplicative. That is, if gcd(m,n) = 1 then phi(mn) = phi(m)phi(n).

    3. Derive a formula for phi(n). Your answer should involve the prime factorization of n = p1k1 · p2k2 · · · prkr.

    4. What is phi(238)?

    5. What is phi(27·35 ·112 ·17)?

These problems are also available as a pdf file.

Solutions

Please email Peter if you are interested in answers or solutions for the web. Thanks.

SOAR Spring 2003 Course Homepage