Rational Numbers. reduced form. (1) a) Show that if

[Pages:1]Math 511, Homework 3 Due: Wednesday, September 12, 2012

Write solutions neatly on a separate sheet of paper. Always start by restating the problem or writing a self explanatory sentence.

(2) 1. Prove that if 1 is a linear combination of two integers a, b, then a and b are relatively prime. Use only basic divisibility properties. (Do not use GCDLC).

2.

Rational

Numbers.

A

rational

number

is

a

real

number

of

the

form

a b

with

a, b Z, b = 0. In this problem we prove that every rational number has a unique

reduced form.

(1) a) Show that if d = gcd(a, b) then gcd(a/d, b/d) = 1. (Use GCDLC theorem and problem 1. Note a/d and b/d are integers.)

(1) reduced

b) Deduce form, that

from part (a) that

is

a b

=

e f

for

some

any

fraction

a b

,

a, b

Z,

can

be

integers e, f with gcd(e, f ) = 1.

expressed

in

b

(2) > 0,

c) Prove gcd(a, b) =

that every 1, that is, if

rational number has a unique reduced

a b

=

c d

with

b

>

0, d

>

0,

gcd

(a, b)

=

1,

form gcd(c,

a

b

d)

with = 1,

then a = c and b = d. (Hint: Use Euclid's Lemma).

(2) 3. Prove by induction that any two consecutive Fibonacci numbers are relatively prime, that is, gcd(Fn, Fn+1) = 1 for all n N. (Recall F1 = 1, F2 = 1, Fn = Fn-1 + Fn-2 for n 3. Hint: Use subtraction principle for gcds.)

(2) 4. a) Basic Primality Test: Let a > 1 be a positive integer such that a is not divisible by any prime p with p a. Prove that a is a prime. (Hint: Do a proof by contradiction. Suppose that a is nota prime, that is, a = bc for some b, c with b = 1 and c = 1. Show that either b a or c a. Say the former holds. What do you conclude about any prime factor of b? )

(1) b) Prove that 197 is a prime using the result of part (a).

(3) 5. Sieve of Eratosthenes: a) Find all of the primes between 200 and 230 by making an array of numbers and then crossing out all multiples of the primes 2,3,5,7, etc. b) Explain why it suffices to cross out just the multiples of primes (for instance why do we not have to test for divisibility by 8 or 21?) c) What is the largest prime divisor that must be considered during the sieve process, according to problem 4?

(2) 6. Irrational Numbers: Prove that if n is not a perfect square then n

is irrational. (Perfect squares are integers of the form m2, withm Z, such

Tashe1n,4,b9y,1p6,r.o..bleHmin2t:b,Donahparsoaofrebdyuccoedntrfoardmictoiof nt.heStuypppeosenth=atab

n is rational. with a, b N,

gcd(a, b) = 1. Deduce that b|a2. Then use Euclid's Lemma to deduce that b = 1.

Conclude that n = a2.)

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

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

Google Online Preview   Download