基礎數論，教我一下這幾題

1.Prove that if a and b are integers , with b > 0, then there exist unique integers q and r satisfying a = qb + r , where 2b &lE; r < 3b

2.Prove or disprove : If a | (b+c) ,then either a | b or a | c

3.If a | bc , show that a | gcd( a , b ) gcd( a , c )

4.Prove that if gcd(a,b)=1 , then gcd( a + b , ab ) =1

1 個解答

• 1 0 年前
最佳解答

1. Prove that if a and b are integers , with b > 0, then there exist unique integers q and r satisfying a = qb + r , where 2b ≦ r < 3b

由Division Algorithm

∃!m，n∈Z such that a=mb+n where 0≤n<b

Then a=(m-2)b+(n+2b)

Say n+2b=r，m-2=q

Since m，n are unique , clearly, q and r are unique

2.Prove or disprove : If a | (b+c) ,then either a | b or a | c

此命題不真，因為5|(2+3)，但5不整除2亦不整除3

3.If a | bc , show that a | gcd( a , b ) gcd( a , c )

Let d1=gcd(a,b) d2=gcd(a,c)

Then by theorem ∃r,s,t,u∈Z such that ar+bs=d1,at+cu=d2

Then d1*d2=(ar+bs)(at+cu)=a(art+rcu+bst)+(bc)su

Since a|bc, a|(bc)su

So a|d1d2

QED

4.Prove that if gcd(a,b)=1 , then gcd( a + b , ab ) =1

First, let gcd(a+b,b)=d

Then d|(a+b) and d|b

Then d|(a+b)-b=a

So d| gcd(a,b), ie d=1

Similarly, gcd(a+b,a)=1

So, by theorem ∃r,s,t,u∈Z such that (a+b)r+bs=1,(a+b)t+au=1

Then 1=[(a+b)r+bs][(a+b)t+au]=(a+b)[rt(a+b)+rau+bst]+(ab)us=1

By thm, gcd( a + b , ab ) =1

參考資料： 我自己+數學娘的加持