Math 115a Number Theory Worksheet With Answers, Hw4
ADVERTISEMENT
1
2MATH 115A Number Theory, HW4
1. Suppose
, as otherwise the formula holds trivially, and let
0 be any integer. I claim the
number of integers
with 1
such that
is [
]. Consider the [
] + 1 intervals of
integers
1 2
+ 1
+ 2
2
2
+ 1
+ 2
3
. .
.
([
]
1)
+ 1 ([
]
1)
+ 2
[
]
[
]
+ 1 [
]
+ 2
The first [
] intervals each has width
, and the last has width
[
] , which would be 0
if
. Observe that
divides precisely one integer in each interval, except the last one, where
does not divide any integers. Thus there are [
] integers
with 1
such that
.
The power of the prime
in the prime power factorization of ! is the sum of all the powers of
in
the prime power factorizations of
for 1
. In other words, the power of
in ! is
+
max
divides
Z
=1
We can rewrite this sum as
+
+1
max
divides
=
#
1 2
divides
but
doesn’t divide
Z
=1
=0
Observe
+1
#
1 2
divides
but
doesn’t divide
=
+1
#
1
divides
#
1
divides
We computed above that
#
1
divides
= [
]
Thus, the power of
in ! is
+1
2
3
[
]
[
] = [
] + [
] + [
] +
=0
2. Suppose otherwise. Suppose there are only + 1 primes of the form 6 + 5, call them
= 5
.
0
1
Let
= 6
+ 5
1
Since
is odd, it must have prime divisors of the form 6 + 5 or 6 + 1. But we know all the primes
of the form 6 + 5, and by construction they do not divide
. Indeed, since 5 doesn’t divide 6
,
1
5 doesn’t divide
; and since
are all bigger than 5, these primes can’t divide 5, hence, can’t
1
divide
. Thus
must be a product of primes of the form 6 + 1. But any product of numbers of the
form 6 + 1 is again of this form, because
(6 + 1)(6 + 1) = 6(6
+ + ) + 1
Thus
must be both of the form 6 + 1 and 6
+ 5, which is a contradiction, because the
1
remainder of
when we divide it by 6 can’t be both 5 and 1.
1
ADVERTISEMENT
0 votes
Related Articles
Related forms
Related Categories
Parent category: Education