Math 3221 Number Theory - Homework Until Test 2 Worksheet With Answers - Philipp Braun Page 4
ADVERTISEMENT
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16¨ ¨
¨ ¨
¨ ¨
¨ ¨
¨ ¨
¨ ¨
r r
¨ ¨
¨ ¨
180 181
182
183
184
785
186
187
188
189
¨ ¨
¨ ¨
¨ ¨
¨ ¨
¨ ¨
¨ ¨
190 191
192 193
194
195
196 197
198 199
(
x means x is divisible by 2, 3, or 5,
x means that x is divisible by 7, 11, or 13.)
¡
e
Thus the primes between 100 and 200 are 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151,
157, 163, 167, 173, 179, 181, 191, 193, 197 and 199.
3. Given that p n for all primes p
n, show that n > 1 is either a prime or the product of
two primes.
Proof. If n was the product of three or more primes, at least one of them had to be less
than or equal to
n. Since by assumption none of the primes p
n divides n, this is a
contradiction. Hence n is a prime or a product of two primes.
4. Establish the following facts:
(a)
p is irrational for any prime p.
(b) If a > 0 and
a is rational, then
a must be an integer.
(c) For n
2,
n is irrational.
a
Proof. (a) Assume
p is rational. Then there are integers a, b with
p =
and
b
2
2
gcd(a, b) = 1. Square the equation and multiply both sides with b to get b
p = a
. That
2
means p a
and since p is a prime p a by Theorem 3.1. Therefore there is an integer c such
2
2
2
2
2
2
that a = cp. Applying that to our first equation, we have b
p = (cp)
= c
p
, or b
= c
p.
2
That means p b
, and again by Theorem 3.1 p b, so p gcd(a, b), a contradiction.
p
p
(b) Assume
a is rational, i.e.
a =
for relatively prime integers p, q. Then a =
.
q
q
n
n
Since p and q are relatively prime, p
and q
are relatively prime, too. That a is an integer
n
forces q
to be 1, so q = 1, i.e.
a = p, an integer.
n
n
n
(c) Since 2
> n for n
2,
2
>
n. But
2
= 2, so
n < 2. On the other hand
n
n > 1 since 1
= 1 < n. By part (b),
n is either an integer or irrational, so
n has to
be irrational as there is no integer between 1 and 2.
5. Show that any composite three-digit number must have a prime factor less than or equal to
31.
Proof. Let c be any composite three-digit number. Since c is composite, there are
integers a, b such that c = ab. Assume a and b are both greater than 31, i.e. at least 32.
5
5
10
Then ab
32 32 = 2
2
= 2
= 1024, which contradicts to the fact that c is a three-digit
number by assumption.
4
ADVERTISEMENT
0 votes
Related Articles
Related forms
Related Categories
Parent category: Education