New York University
[Link] 110 Quantitative Reasoning: Great Ideas in Mathematics
Problem Set 2
This problem set consists not only of problems similar to what you’ve seen, but also of
unique problems you may not have seen before. The purpose of the latter is for you to apply
the concepts you’ve previously learned to new, unfamiliar, and usually more interesting
situations. In some cases, problems connect ideas from multiple learning objectives.
Write full, clear solutions to the problems below. It is important that the logic of how you
solved these problems is clear. Although the final answer is important, being able to con-
vey you understand the underlying concepts is more important. The point weight of each
problem is indicated prior to each question. This problem set is graded out of 50 total points.
Proofs. Be sure to define all your variables and make conclusions based on definitions from
class or past proofs.
1. (5 points) Suppose a 2 Z. Prove that a2 has remainder 0 or remainder 1 upon division
by 4.
Let a E Z .
We can where
say a =
4g + r
,
r can be 0 , 1,2 , or 3 .
Cas a =
4g to → a =
49
Then a
2 =
(4g ) 2
= 2
16g
414g 2)
=
Since
492 Ez ,
r = 0 .
✓
Case a =
49+1
2
Then a
2 =
( 4g + 1)
=
1692+89+1
(492+29)+1
=
4
Since
492+89 C- 27
,
r =
1 . ✓
2. (6 points) If we divide a square integer by 3, prove that the remainder cannot be 2.
Let a E Z so that a 213 .
We can
say a =3
qtr ,
where r can be 0 1 or 2
, ,
.
Case 1 →
3g to
3g
=
: a =
a
-
Then , 2
a 2 =
g)
=
992
=3 ( 392)
since 392€27 r = 0 .
Case2 a =
39+1
Then a 2 =
(3g + 1) 2
,
992+69+1
=3 (392+29)+1
since 392 +2g E E 1
r =
.
,
Case 3 :
3g
=
-
a +2
Then a
2=(39+2) 2
=
992+129+4
=3 (392+49)+40
r
3. (5 points) Let m be a positive integer. Prove that gcd(m, m + 2) is either 1 or 2.
Let ME 27 m ≥/
,
gcd (m ,
Mt 2)
Case 1 :
m = n +1
-
Then
gcd ( 2n +1,2 @ 1) 2) + +
=
gcd ( Zntl , 2h + 3)
gcd ( (1) +1,2 (1) +3)
= 2
=
gcd ( 3. 5) =/ ✓
Casm=2n
Then gcd ( 2h 2h +2 )
,
=
god ( zu ) , 2( 1) + 2)
=gcd ( 2,4 ) =
2 ✓
Exercises. Show all of your work in a clear, logical manner.
4. (4 points) Following the Division Algorithm, rewrite the following pairs of a and b in
the form a = bq + r.
(a) a = 56, b = 9
56=99
+ r
56=9CG)+zI
(b) a = 23, b = 10
-23=109 + r
_23=lO(-3)tI
(c) a = 102, b = 5
102=59 +r
102=51203+2-1
(d) a = 55, b = 11
55=119 + r
55=1167+38
5. (4 points) Find the prime factorization for the following integers.
(a) 252
/\ 22i3
2 126
/ 1
2 63
/ I
7 9
11
3 3
(b) 864
11
2 432
/
2
\
216 25.33J
/ \
2 108
11
2 54
/ \
2 27
"
(c) 101 31 9
/ I
33
⑤
(d) 4, 080
/ \
5 816
/ \
2
408
/ \
2+.3.5
2 204
/ \
2 102
11
2 51
/ 1
3 17
6. (3 points) Construct an infinite list of natural numbers, all of which are not prime.
Write your answer using set builder notation.
A=
{ 2n in c- IN
}
A-
{ K2
=
K
}
n =
≥2
,
: K n C-
,
IN
7. (3 points) Construct a set of of 321 consecutive integers, all of which are composite.
Write your answer using set builder notation. Provide a brief explanation why each of
the elements in that set are indeed composite.
A
{
=
a ! + b : a c- IN BEZ , ≥3 321 ≥ b ≥ 2
}
,
a
,
a cannot be an
integer because 0 cannot be factored . a has to be
greater than 3 because 2 ! is
prime b is
greater than 2 because
.
we
do not know if + I will make it
composite .
8. (5 points) Use the Euclidean Algorithm to find gcd(4709, 6188).
god ( 4709,6188 )
4709
-
=
god ( 4709,1479 )
1479 (3)
-
=
gcd ( 272,1479 )
272 (5)
-
=
gcd ( 272 ,
119 )
-
119 (2)
god ( )
=
34 119
,
34 (3)
-
=gcd( 34 ,
17 ) =
9. (5 points) Suppose a certain number when divided by 91 yields a remainder of 53. If we
add 105 to our original number, what is the remainder when this new number is divided
by 91?
a
=
919+53 at 105--53+105=158
a
=
91 ( o ) +53 158 mod 91 =
④
a
=
53
10. (6 points) Compute the following. Show your work by “reducing” each term in the sum
or product.
(a) 5 +12 9
(5 mod 12 + 9 mod I
2) mod 12
=
(5+9) mod 12
I 4 mod 12
= =
(b) 5 +6 9
(5 mod 6 + 9 mod 6) mod 6
=
( 5 +
3) mod 6
= 8 mod 6 =
(c) 5 +7 9
(5 mod 7 +9 mod 7) mod 7
=
( 5 +
2) mod 7
=
7 mod 7 =
②
(d) 15 ·12 146
(15 mod 12 .
146 mod / 2) mod 12
120
-
=
( 15 mod 12 -
26 mod /2) mod 12
-
12 -
24
( 3 mod 12 / 2) mod
12=(3-2) mod 12=6mod 12 ⑥
=
2 mod
.
(e) 15 ·5 146
(15 mods -
146 mod 5) mods
=
( On 146 mod 5) mods
=
0 mod 5 =
③
(f) 15 ·2 146
( 15 mod 2 •
146 mod 2) mod 2
=
( 15mod 2 .
0 ) mod 2
= ☐ mod 2 =
②
11. (4 points) Compute the following. Show your work by “reducing” each term in the sum
or product. Hint: there are shortcuts/fast ways to compute these; think about how!
(a) 3245 +3 +9823 +3 969696 +3 ( 3458)
W w
T -
f
"
3+2+4+5=14
l
4mod3=②
9+8+2+3=22
22 mod 3
9+6+9+6 +9+6=45
45mn13 ⑤
-
3 -4-5-8=-20
-
20 mod 3 =
①
2 + I + 0+1 =
☒
(b) 121 ·11 342234 ·11 47389 ·11 89381
w
121 mod / 1=0
O '
342234 mod 11 •
47389 mod / I -
89381 mod 11
=
③