SOLUTIONS TO HOMEWORK 2 - MATH 170, SUMMER SESSION I (2012)

SOLUTIONS TO HOMEWORK 2 - MATH 170, SUMMER SESSION I

(2012)

(1) (Exercise 11, Page 107) Which of the following is the correct UPC for Progresso

minestrone soup? Show why the other numbers are not valid UPC¡¯s.

0 41196 01012 1

0 52010 00121 2

0 05055 00505 3

Note: UPC stands for Universal Product Code, which is basically the product bar

codes we had been discussing in lectures.

Solution : For the first one, without the check digit,

3 ¡¤ 0 + 4 + 3 ¡¤ 1 + 1 + 3 ¡¤ 9 + 6 + 3 ¡¤ 0 + 1 + 3 ¡¤ 0 + 1 + 3 ¡¤ 2 mod 10

= 4 + 3 + 1 + 27 + 6 + 1 + 1 + 6 mod 10

= 49 mod 10 = 9.

Clearly the check digit, 1, adds up to 9 to give 0 mod 10. Hence, this is a UPC

indeed.

For the second one, without the check digit,

3 ¡¤ 0 + 5 + 3 ¡¤ 2 + 0 + 3 ¡¤ 1 + 0 + 3 ¡¤ 0 + 0 + 3 ¡¤ 1 + 2 + 3 ¡¤ 1 mod 10

= 5 + 6 + 3 + 3 + 2 + 3 mod 10

= 22 mod 10 = 2.

But the check digit here is 2, and 2 + 2 mod 10 = 4 6= 0. So, this is not a UPC.

For the third one, without the check digit,

3 ¡¤ 0 + 0 + 3 ¡¤ 5 + 0 + 3 ¡¤ 5 + 5 + 3 ¡¤ 0 + 0 + 3 ¡¤ 5 + 0 + 3 ¡¤ 5 mod 10

= 15 + 15 + 5 + 15 + 15 mod 10 = 5

mod 10.

But the check digit is 3, and 5 + 3 mod 10 = 8 6= 0 So, this is not a UPC.

(2) (Exercise 13, Page 107) The following is the UPC for Hellman¡¯s 8 oz. Real Mayonnaise. Find the missing digit.

0 48001 26 04 2

1

2

SOLUTIONS TO HOMEWORK 2 - MATH 170, SUMMER SESSION I (2012)

Solution : Let us call this missing digit x. Then, without the check digit,

3 ¡¤ 0 + 4 + 3 ¡¤ 8 + 0 + 3 ¡¤ 0 + 1 + 3 ¡¤ 2 + 6 + 3x + 0 + 3 ¡¤ 4 mod 10

= 4 + 24 + 1 + 6 + 6 + 3x + 12 mod 10

= 53 + 3x mod 10 = 3 + 3x mod 10.

Now, we must have that, 3 + 3x + 2 mod 10 = 0, i.e., 5 + 3x mod 10 = 0. This is

possible only if x = 5 which gives us the missing digit.

(3) A bank identification number is a 9 digit number that occurs in the lower left hand

corner of bank checks. Let the digits be n1 , n2 , n3 , n4 , n5 , n6 , n7 , n8 , n9 . For a 9

digit number to be a valid bank identification number, it must satisfy

7n1 + 3n2 + 9n3 + 7n4 + 3n5 + 9n6 + 7n7 + 3n8 + 9n9 ¡Ô 0

mod 10.

(Exercise 21, Page 108) Determine the check digits (i.e. last digits) of the following

bank codes:

3 1 0 6 1 4 8 3

0 2 5 7 1 1 0 8

Solution : Let us call the check digit c. In the first code, we need,

7 ¡¤ 3 + 3 ¡¤ 1 + 9 ¡¤ 0 + 7 ¡¤ 6 + 3 ¡¤ 1 + 9 ¡¤ 4 + 7 ¡¤ 8 + 3 ¡¤ 3 + 9c ¡Ô 0

=? 21 + 3 + 0 + 42 + 3 + 36 + 56 + 9 + 9c ¡Ô 0

=? 0 + 9c ¡Ô 0 mod 10.

mod 10.

mod 10.

So, the digit c needed to make 9c ¡Ô 0 mod 10 is 0. So, in the first code, the check

digit is 0.

In the second code, we need,

7 ¡¤ 0 + 3 ¡¤ 2 + 9 ¡¤ 5 + 7 ¡¤ 7 + 3 ¡¤ 1 + 9 ¡¤ 1 + 7 ¡¤ 0 + 3 ¡¤ 8 + 9c ¡Ô 0 mod 10.

=? 0 + 6 + 45 + 49 + 3 + 9 + 0 + 24 + 9c ¡Ô 0 mod 10.

=? 6 + 9c ¡Ô 0 mod 10.

Now, the digit c needed to make 6 + 9c ¡Ô 0 mod 10 is 6. So, in the second code,

the check digit is 6.

(4) Show that the following statements are true:

(a) 547 ¡Ô 6 ¡Á 17 mod 23.

Solution : By Fermat¡¯s Little Theorem, 523?1 ¡Ô 1 mod 23. That is, 522 ¡Ô 1

mod 23. We can now square both sides to get, 544 ¡Ô 1 mod 23. Multiplying

both sides by 53 , we get, 544+3 ¡Ô 53 mod 23. That is, 547 ¡Ô 125 mod 23.

Now, 125 = 115 + 10 = 3 ¡Á 23 + 10. So, 125 mod 23 is 10. Therefore, 547

mod 23 = 10.

SOLUTIONS TO HOMEWORK 2 - MATH 170, SUMMER SESSION I (2012)

3

Next, 6 ¡Á 17 = 102 = 92 + 10 = 23 ¡Á 4 + 10 and so, 6 ¡Á 17 mod 23 = 10.

Thus, 547 ¡Ô 6 ¡Á 17 mod 23.

(b) 42 ¡Á 33 ¡Ô 251 mod 13.

Solution : By Fermat¡¯s Little Theorem, 213?1 ¡Ô 1 mod 13, that is, 212 ¡Ô 1

mod 13. Taking a power of 4, 248 ¡Ô 1 mod 13. So, multiplying by 23 = 8 on

both sides, 251 ¡Ô 8 mod 13. That is, 251 mod 13 = 8.

Next, 42 ¡Á 33 mod 13 = 16 ¡Á 33 mod 13 = (13 + 3) ¡Á (26 + 7) mod 13 = 3 ¡Á 7

mod 13 = 21 mod 13 = 8. Thus, 42 ¡Á 33 ¡Ô 251 mod 13.

(5) Carefully look at the following mathematical reasoning. Write down what is wrong

with it.

I believe that 6832 ¡Ô 1 mod 17. This is because, Fermat¡¯s theorem says that

if p is prime, ap?1 ¡Ô 1 mod p, and since 17 is a prime with 17 ? 1 = 16, we must

have, 6816 ¡Ô 1 mod 17. Taking a power of 2 on both sides of the congruence, we

get, 6832 ¡Ô 1 mod 17.

After you have answered what is the mistake above, write down the correct number

between 0 and 16 that is 6832 mod 17.

Solution : Fermat¡¯s little theorem says that if p is prime and a is an integer

N OT DIV ISIBLEBY p, then, ap?1 ¡Ô 1 mod p. Although, 17 is prime here,

68 is indeed divisible by 17 (17 ¡Á 4 = 68), and so Fermat¡¯s Little Theorem does not

apply here.

The correct answer should be 6832 mod 17 = 0. This is because, as 17 divides

68, 17 will divide any power of 68, and so, 17 divides 6832 .

(6) Prove the following statements using the principle of induction:

(a) 1 + 3 + 5 + ... + (2n ? 1) = n2 , for all natural numbers n.

Solution : The statement S(n) is ¡°1 + 3 + 5 + ... + (2n ? 1) = n2 ¡±.

Step 1: We check if this is true for n = 1. The left hand side is just 1,

and the right hand side is 12 and hence is 1. So, S(1) is true.

Step 2: We assume S(m) is true. That is, we assume, 1+3+...+(2m?1) = m2 .

Step 3: Now we need to prove that S(m + 1) is true. That is, we need

4

SOLUTIONS TO HOMEWORK 2 - MATH 170, SUMMER SESSION I (2012)

to prove that 1 + 3 + ... + (2(m + 1) ? 1) = (m + 1)2 . The left hand side is

1+3+...+(2m+1) = 1+3+5+...+(2m?1)+(2m+1) = m2 +2m+1 (from Step

2). But, m2 +2m+1 = (m+1)2 . Therefore, 1+3+...+(2(m+1)?1) = (m+1)2 ,

which completes our induction steps.

Hence, by induction, the statement 1 + 3 + 5 + ... + (2n ? 1) = n2 is true

for all natural numbers n.

(b) 32n?1 + 2n+1 is divisible by 7, for all natural numbers n.

Solution : The statement S(n) is ¡°32n?1 + 2n+1 is divisible by 7¡±.

Step 1: We check if this is true for n = 1. 32¡Á1?1 + 21+1 = 3 + 22 = 3 + 4 = 7,

which of course is divisible by 7. So, S(1) is true.

Step 2: We assume S(m) is true. That is, we assume, 32m?1 + 2m+1 is divisible by 7. So, there is an integer k for which, 32m?1 + 2m+1 = 7k. Then,

2m+1 = 7k ? 32m?1 .

Step 3: Now we need to prove that S(m + 1) is true. That is, we need to

prove that 32(m+1)?1 + 2(m+1)+1 is divisible by 7. Now,

32(m+1)?1 + 2(m+1)+1 = 32m+1 + 2m+1 ¡¤ 2

= 32m+1 + (7k ? 32m?1 ) ¡¤ 2, (from Step 2)

= 14k + 32m+1 ? 2 ¡¤ 32m?1 ,

= 14k + 32m?1+2 ? 2 ¡¤ 32m?1 ,

= 14k + 32m?1 (32 ? 2) = 14k + 32m?1 ¡¤ 7,

which, of course, is divisible by 7. This completes our induction steps.

Hence, by induction, 32n?1 + 2n+1 is divisible by 7, for all natural numbers n.

(c) Let Fn denote the nth Fibonacci number (so, F1 = 1, F2 = 1, F3 = 2, F4 = 3

and so on). Show that

F12 + F22 + ... + Fn2 = Fn ¡¤ Fn+1 , for all natural numbers n.

Solution : The statement S(n) is ¡°F12 + F22 + ... + Fn2 = Fn ¡¤ Fn+1 ¡±.

Step 1: We check if this is true for n = 1. The left hand side F12 , which

is just 1, and the right hand side is F1 ¡¤ F2 = 1 ¡¤ 1 = 1. So, S(1) is true.

SOLUTIONS TO HOMEWORK 2 - MATH 170, SUMMER SESSION I (2012)

5

2 =

Step 2: We assume S(m) is true. That is, we assume, F12 + F22 + ... + Fm

Fm ¡¤ Fm+1 .

Step 3: Now we need to prove that S(m + 1) is true. That is, we need

2

to prove that F12 + F22 + ... + Fm+1

= Fm+1 ¡¤ Fm+2 . The left hand side is

2

2

2

2

2

F1 + F2 + ... + Fm + Fm+1 = Fm ¡¤ Fm+1 + Fm+1

= Fm+1 (Fm + Fm+1 ). Now,

because Fn is the nth Fibonacci number, Fm + Fm+1 = Fm+2 . Therefore,

2

F12 + F22 + ... + Fm+1

= Fm+1 ¡¤ Fm+2 , which completes our induction steps.

Hence, by induction, the statement F12 + F22 + ... + Fn2 = Fn ¡¤ Fn+1 is true

for all natural numbers n.

(7) Prove the following statements using the method of contradiction:

(a) The negative of an irrational number is irrational.

Solution : Let x be an irrational number. Assume that ?x is rational. So, we

can write ?x as pq where p, q are integers with q 6= 0. Thus,

?x =

p

q

=? x = ?

p

?p

=

.

q

q

Since ?p and q are still integers, with q 6= 0, x is a rational number, which is

a contradiction. Hence, the negative of an irrational number is irrational.

(b) There are no even primes that are bigger than 2.

Solution : Suppose there are even primes bigger than 2. Let p be one such

prime. Since p is even, this means that we can write p = 2k for some natural

number k > 1. But, this implies that both 2 and k divide p, which is a contradiction, since p is prime. Hence, there are no even primes that are bigger

than 2.

(c)

¡Ì

6 is irrational. ¡Ì

Solution : Assume 6 is rational. Then we can write,

¡Ì

p

6= ,

q

where p and q are integers that have no common factors, and q 6= 0. Squaring

both sides,

p2

,

q2

6q 2 = p2 .

6=

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download