Algebraic Manipulation Worksheets With Answers - Serge Ballif Page 2
ADVERTISEMENT
1
2
3Serge Ballif
MATH 567 Homework 1
Tuesday, September 2, 2008
Harder Problems
5. Prove that every positive integer is uniquely expressible in the form
j
j
j
j
2
2
2
2
0
1
2
m
where m
0 and 0
j
j
j
j
.
0
1
2
m
The proof is by induction. Let S (n) be the statement “each positive integer less than
n
0
2
1 can be written in the desired form.” The base case S (1) is true as 1
2
is the
unique way to express 1 as a sum of powers of 2.
n 1
n
Suppose now that S (n 1) is true. Let k be a number in the range 2
k
2
1.
n 1
By the induction hypothesis k
2
is uniquely expressible in the form
n 1
j
j
j
j
k
2
2
0
2
1
2
2
2
m
n 1
Adding 2
to both sides gives a way of expressing k as a sum of distinct powers of
2. The uniqueness of this expression is guaranteed by the uniqueness of the sum for
n 1
k 2
, since two di erent expressions for k would result in two di erent expressions
n 1
for k
2
. This shows that S (n) holds true if we assume S (n
1). By mathematical
induction S (n) holds for all n.
6. Prove that there are no positive integers a, b, n with n
1 such that
n
n
n
n
(a
b
) (a
b
)
n
n
n
n
a
b
a
b
n
n
n
n
(a
b
) (a
b
) if and only if
. Hence we need only prove the result
n
n
(a b)
(a b)
n
n
a
b
when (a b)
1. Seeking a contradiction, we assume that
is an integer. Then the
(a b)
calculation
n
n
n
n
n
n
n
a
b
a
b
b
b
2b
1
n
n
n
n
n
n
a
b
a
b
a
b
n
n
n
n
n
shows that a
b
must divide 2b
. From this we conclude that a
2b
. Since a and
n
b have no common factors, then a
must divide 2. This can’t happen for n
1, so we
have arrived at a contradiction. Hence the result holds.
7. Prove that any positive integer of the form 4k
3 has a prime factor of the same form, and similarly for the form
6k
5. Deduce that there are infinitely many primes of the form 4k
3 and similarly for 6k
5.
Let n
4k
3 be a positive integer. If n is prime, then we are done. Suppose that n is
not prime. Then n factors into a product of odd primes n
p
p
p
. The product of
1
2
r
numbers of the form 4k
1 is another number of the form 4k
1. Hence some p
is of
i
the form p
4k
3.
i
Let n
6k
5 be a positive integer. If n is prime, then we are done. Assume that
n is not prime. Then n is a product of odd prime factors n
p
p
p
. The product
1
2
r
of numbers of the form 6k
1 is another number of the form 6k
1. A product of a
number of the form 6k 1 or 6k 3 with a number of the form 6k 3 is another number
of the form 6k
3. Hence some p
is of the form p
6k
5.
i
i
Page 2 of 3
ADVERTISEMENT
0 votes
Related Articles
Related forms
Related Categories
Parent category: Education