[PDF] [PDF] SOLUTIONS TO PROBLEM SET 1 Section 13 Exercise 4 We see
previous paragraph This shows that a = 1,2 have an unique balanced ternary expansion that p > n In particular, given a positive integer n we can always find a prime larger than n; by growing n Since (12,18) = 6 50 there are no solutions
1 Proof We prove the result for the case when n is multiplicatively e-perfect, the other prime number p, 2p-multiplicatively e-superperfect numbers which have the Te((p1 · p2)2p)=(p1 · p2)σ(2p)·d(2p) = (p1 · p2)3·(p+1)·4 = (p1 · p2)12·(p+1)
17 mai 2016 · Proof Let p be an integer such that 2p − 1 is a prime number We aim to show that all perfect numbers of the form 2p-1(2p − 1)? The next significant step in the answering of σ(6) = 1 + 2 + 3 + 6 = 12 σ(18) = 1 + 2 + 3 + 6 +
Roots that a perfect number other than 6 has digital root 1 We now provide a proof of this claim 12 is abundant, because 1 + 2 + 3 + 4 + 6 + 12 > 24 For, if p is a prime number, then 12p is necessarily an abundant number, because
Theorem 1 1f the number (2"-1) 18 prime, then the number 2n-1/2"-1) is Proof Let p = (2"-1) and suppose p 18 prime Then the 1 e (2"-1)(1+p) This equals 12"-1)2", One could say that m is perfect if the sum of all the factors of in, which is
previous paragraph This shows that a = 1,2 have an unique balanced ternary expansion that p > n In particular, given a positive integer n we can always find a prime larger than n; by growing n Since (12,18) = 6 50 there are no solutions
e-superperfect numbers and prove some results on them We also p = 1 It is impossible since p is a prime number If at least an αi is equal to 1, say α1 = 1, then from (2 2), we 2 be the prime factorisation of an integer n > 1 where p1 and p2 are r = 1: (3 3) becomes 2 · (α1 + 1) = 12 · (2p − 1); it gives α1 = 12p − 5
We show that no Fibonacci number (larger than 1) divides the sum of its divi- sors 2 Notation For a positive integer a and a prime p we write p a/ for the exact [ 3] and [21] we get that n0 2 ¹1; 2; 3; 4; 6; 12º, so n 2 ¹3; 6; 9; 12; 18; 36º, and the
greater than 10 contains a prime number greater than or equal to 11, which is impossible And from 1,2, ,10 we cannot select nine consecutive numbers with the required We need the fact that every integer p ≥ 2 can be represented as a2 + b2 Methods of Proof 335 1 = 12, 2 = −12 − 22 − 32 + 42, 3 = −12 + 22,
;11?2+12?3=23 ;11?2+12?3+13?4=34 and is reasonable to conjecture n k=11k(k+1)=nn+1:
We will prove this formula by induction.
Basen=1:It is shown above.
Hypothesis:Suppose the formula holds forn.
Step: n+1 k=11k(k+1)=n k=11k(k+1)+1(n+1)(n+2) nn+1+1(n+1)(n+2) n(n+2)+1(n+1)(n+2)=n2+2n+1(n+1)(n+2) (n+1)2(n+1)(n+2)=n+1n+2; where in the second equality we used the induction hypothesis.
Exercise 14.We will use strong induction.
and
58=7?4+10?3;59=7?7+10?1;60=7?0+10?6:
Stepn≥60?We haven-6≥54, hence by the induction hypothesis we can write n-6=7a+10bfor somea;b?Z>0:
Thenn+1=7(a+1)+10b, as desired.
1
Exercise 22.We will use induction.
Basen=0:We have1+0h=1=(1+h)0, as desired.
Hypothesis:Suppose the result holds forn.
Stepn≥0?We have
(1+h)n+1=(1+h)n(1+h) ≥(1+nh)(1+h) =1+h+nh+nh2 ≥1+(n+1)h; where in the first inequality we used the induction hypothesis and1+h≥0. Exercise 24.The proof fails in the statement that the sets{1;:::;n}and{2;:::;n+1} have common members. This is false whenn=1; indeed, the sets are{1}and{2}which are clearly disjoint.
Section 1.5
Exercise 26.Leta;b?Z>0.
We first proveexistence. The division algorithm givesq′;r′?Zsuch that
We now divide into two cases:
(ii) Supposeb?2Writeq=q′+1andr=r′-b. Then as desired.
We now proveuniqueness. Suppose
Thenb(q1-q2)=(r2-r1)andbdividesr2-r1. Since-b2-r1=0because there is no other multiple ofbin this interval. We conclude thatr1=r2 andb(q1-q2)=0; thus we also haveq1=q2, as desired. Exercise 36.Leta?Z. Dividingaby 3 we geta=3q+rwithr=0;1;2. Note that a
3-a=(a-1)a(a+1)=(3q+r-1)(3q+r)(3q+r+1)
and clearly for any choice ofr=0;1;2one of the three factors is a multiple of 3. This is the same as saying that in among three consecutive integers one must be a multiple of 3. 2
Section 2.1
Exercise 12.Leta?Z>0.
We first proveexistence. We will use strong induction. Hypothesis:Suppose the desired expression exists for all positive integers0?Zsuch that in particular,r=-1;0;1. We have0Thus we have and we takek=s+1,e0=randei=as-1fori=1;::;k. We now proveuniqueness. We will use strong induction. Suppose a=ek3k+:::+e13+e0=cs3s+:::+c13+c0; ek;as≠0; ei;ai?{-1;0;1}: can takek=1,e1=1ande0=-1, as balanced ternary expansions. Note also that0cannot be written as an expansion using non-zero coefficients. Suppose nowa=1=ek3k+:::+e13+e0withk≥1; thenadivided by 3 has remindere0=1 by the division algorithm. We conclude thatek3k+:::+e13=0which is impossible, unless e i=0for alli≥1. Supposea=2=1?3-1=ek3k+:::+e13+e0withk≥1; thenadivided by 3 has reminder e
0=-1by the modified division algorithm. We conclude thatek3k+:::+e13=3. Dividing
both sides by 3 we conclude thatek3k-1+:::+e1=1which givesk=1ande1=1by the previous paragraph. This shows thata=1;2have an unique balanced ternary expansion. Hypothesis:Suppose the expansion is unique for all positive integers0and (due to the symmetry of the coefficients) we obtain the expansion foraby multiplying by-1the expansion for-a. Exercise 13.Letwbe the weight to be measured. From the previous exercise we can write w=ek3k+:::+e13+e0; ek≠0; ei?{-1;0;1}: Place the object in pan 1. Ifei=1, then place a weight of3iinto pan 2; ifei=-1, then place a weight of3iinto pan 1; ifei=0do nothing; in the end the pans are balanced. 3
Exercise 17.Letn?Z>0be given in basebby
Letm?Z>0. We want to find the basebexpansion ofbmn, that is b Multiplying both sides of the first equation bybmgives b We know that the expansion in basebis unique, so by comparing the last two equations we conclude that s=k+m; cs-i=ak-ifori=0;:::;kandci=0fori=0;:::;m-1; which means b where we havemzeros in the end.
Section 3.1
Exercise 6.Letn?Z. Note the factorizationn3+1=(n+1)(n2-n+1)into two integers. Ifn3+1is a prime, thenn≥1andn+1is either1or prime. Sincen+1≠1we haven+1is prime and hencen2-n+1must be 1, which impliesn=0;1. We concluden=1, as desired. Exercise 8.Letn?Z>0. ConsiderQn=n!+1. There is a prime factorp?Qn. Suppose thatp>n. In particular, given a positive integernwe can always find a prime larger than n; by growingnwe produce infinitely many arbitrarily large primes. p? (n!-Sn)=1, a contradiction. Thusp>n. Because we can find arbitrarily large primes, there must be infinitely many.
Section 3.3
Exercise 6.Leta?Z>0and writed=(a;a+2). In particular,ddivides bothaanda+2, hencedalso divides the difference(a+2)-a=2. We concluded=1ord=2. Now, ifais odd thena+2is also odd, henced=1; ifais even then2divides bothaanda+2, sod=2. We conclude that(a;a+2)=1if and only ifais odd and(a;a+2)=2if and only ifais even. Exercise 10.Writed=(a+b;a-b). Ifd=1there is nothing to prove. Supposed≠1and let pbe a prime divisor ofd(which exists becaused≠1). In particular,pis a common divisor ofa+banda-b, therefore it divides both their sum and difference; more precisely,pdivides (a+b)+(a-b)=2aand(a+b)-(a-b)=2b:
Furthermore, sincepis prime we also have
(i)p?2aimpliesp=2orp?a, 4 (ii)p?2bimpliesp=2orp?b. Supposep≠2. Then in (i) we havep?aand in (ii) we havep?b; this is a contradiction with (a;b)=1. We conclude thatp=2. So far we have shown that the unique prime factor ofdis 2, therefored=2kwithk≥1. To finish the proof we need to prove thatk=1. Sinced?a+bandd?a-barguing as above we conclude that2k?2aand2k?2b, that is
2a=2kxand2b=2kyfor somex;y?Z:
Supposek≥2. Then dividing both equations by 2 we get a=2k-1xandb=2k-1y withk-1≥1. In particular2?aand2?b, a contradiction with(a;b)=1, showing thatk=1, as desired. Here is an alternative, shorter proof using one of the main theorms ongcd: Leta;b?Zsatisfy(a;b)=1. There existx;y?Zsuch thatax+by=1. Then (a+b)(x+y)+(a-b)(x-y)=2ax+2by=2(ax+by)=2 and since(a+b;a-b)is the smallest positive integer that can be written as an integral linear desired. Exercise 12.Leta;b?Zbe even and not both zero. There existx;y?Zsuch that ax+by=(a;b)?a2 x+b2 y=(a;b)2 Since(a?2;b?2)is the smallest positive integer that can be written as an integral linear To finish the proof we will show that(a?2;b?2)≥(a;b)?2. There existx;y?Zsuch that a2 x+b2 y=(a?2;b?2)?ax+by=2(a?2;b?2): Since(a;b)is the smallest positive integer that can be written as an integral linear combi- nation ofaandbwe conclude(a?2;b?2)≥(a;b)?2, as desired. Exercise 24.Letk?Z>0. Supposedis a common divisor of3k+2and5k+3. Thend divides every integral linear combination of these numbers. In particular,ddivides
5(3k+2)-3(5k+3)=15k+10-15k-9=1;
hence(3k+2;5k+3)=1, as desired. 5
Section 3.4
Exercise 2.We will use the Euclidean algorithm.
a) Compute(51;87). thus(51;87)=3. b) Compute(105;300).
300=105?2+90;105=90?1+15;90=15?6+0;
thus(105;300)=15. c) Compute(981;1234). and
222=31?7+5;31=5?6+1;5=1?5+0;
thus(981;1234)=1.
Exercise 6.
a) Compute(15;35;90).
Note that90=15?6then((15;90);35)=(15;35)=5.
b) Compute(300;2160;5040). Note that1260=300?7+60and300=60?5thus(300;2160)=60.
Since5040=60?84we also have
Section 3.5
Exercise 10.Leta;b?Z>0. Supposea3?b2.
Writea=pa11pa22:::pakkfor the prime factorization ofa. Writepbiifor the largest power ofpi
2bi-3ai≥0, hencebi?ai≥3?2>1. Thusbi>aifor alli. Hence we can write
for somem′?Z(note thatm′is needed sincebmay have prime factors which are none of thepi). Therefore, by reordering the factors we also have
Thusa?b, as desired.
6 Exercise 30.We will use the formulas for(a;b)andLCM(a;b)in terms of the prime factorizations ofaandb. a)a=2?32?53,b=22?33?72. Thus (a;b)=2?32;LCM(a;b)=22?33?53?72: b)a=2?3?5?7,b=7?11?13. Thus (a;b)=7;LCM(a;b)=2?3?5?7?11?13: c)a=28?36?54?1113,b=2?3?5?11?13. Thus d)a=41101?4743?1031001,b=4111?4347?83111. Thus
Exercise 34.Leta;b?Z>0. Suppose that
(a;b)=18=2?32andLCM(a;b)=540=22?33?5: Since(a;b)?LCM(a;b)=abwe conclude that the possible prime factors ofa,bare 2, 3 and
5. Write
a=2d23d35d5; b=2e23e35e5; di;ei≥0 for the prime factorizations ofaandb. We also know that and
Therefore,
min(d2;e2)=1max(d2;e2)=2: After interchanginga;bif necessary we can supposed2=1ande2=2. Similarly, we also have Thus(d3;e3)=(2;3)or(3;2)and(d5;e5)=(1;0)or(1;0), giving the following four possi- bilities fora;b: (1)a=21?32=18andb=22?33?51=540, (2)a=21?32?51=90andb=22?33=108, (3)a=21?33=54andb=22?32?51=180, (4)a=21?33?51=270andb=22?32=36, Since(a;b)andLCM(a;b)do not depend on the signs and order ofa;bwe obtain all the so- lutions by multiplyingaorbor both by-1and interchanging them:(±18;±540),(±540;±18), The following argument, avoiding the formula(a;b)?LCM(a;b)=ab, is an alternative to the first part of the proof above. Write a=pe11:::pekk; b=pd11:::pdkk; ei;di≥0 7 (note that we have to allow the exponents to be zero so that we can use the same primespi in both factorizations). We have that
k; hence max(e1;d1)=2, max(e2;d2)=3,p3=5, max(e3;d3)=1and max(ei;di)=0for alli at the same time that the prime factors ofaandbare2,3or5and information about the possible exponents they may occur.
Exercise 42.
(a)Suppose3⎷5is rational. Then,3⎷5=a?bfor some coprime positive integersa;bwith b≠0. Then, we have
3⎷5=a?b??5b3=a3??5?a
because5is a prime dividing the producta3=aaa, so divides one of the factors. Therefore, a=5kfor somek?Zand, replacing above gives
5b3=(5k)3??b3=52k3??5?b;
showing that botha;bare divisible by 5, a contradiction. (b)Letf(x)=x3-5, which is a monic polynomial with integer coefficients. We have f(3⎷5)=0and since3⎷5is not an integer it must be irrational by Theorem 3.18 (in the textbook). Exercise 45.Suppose thatlogpbis rational. Then,logpb=r?qfor some coprimer;q?Z withq≠0. Then, qlogpb=r??(plogpb)q=pr??bq=pr and sincebis not a power ofpit must be divisble by some other primeq. Thenq?pr, a contradiction sincepis prime.
Exercise 56.We will work by contradiction.
Suppose there are only finitely many primes of the form6k+5. Denote themp0=5;p1;:::;pk and consider the number
N=6p0p1⋯pk-1:
ClearyN>1becausep0=5, so there exists a prime factorpdividingN. We apply the division algorithm to dividepby 6 and obtain
We now divide into cases
impossible; thusr≠0;2;4. (3) Supposer=5; thuspis of the form6k+5and by hypothesis we havep=pifor somei. Sincepi?N+1it does not divideN, again a contradiction. 8 From these cases it follows thatpis of the form6k+1. Sincepis any prime factor ofN, we conclude that all the prime factors occrring in the prime factorization ofNare of the form
6k+1. In other words,
N=`a11?:::?`asswith`i=6ki+1distinct primes andai≥1: Note that(6k+1)(6k′+1)=6(6kk′+k+k′)+1, that is the product of any two integers of the form6k+1is also of this form. From the prime factorization above we conclude thatN is of the form6k+1. This is incompatible withNbeing also of the form6k-1as defined above. Thus our initial assumption is wrong, i.e. there are infinitely many primes of the form6k+5, as desired. If you are familiar with congruences the last part of the proof can be restaded as follows.From the cases it follows that any primeqdividingNis of the form6a+1, that isq≡1(mod 6). Since the product of two such primesq1,q2(not necessatily distinct) also satisfiesq1q2≡1(mod 6)we conclude thatN≡1(mod 6)which is a contradiction with
N≡-1≡5(mod 6).
Section 3.7
Exercise 2.We apply the theorem we learned in class to describe solutions of linear Dio- phantine equations. a) The equation3x+4y=7.Since(3;4)=1?7there are infinitely many solutions; note thatx0=y0=1is a particular solution. Then all the solutions are of the form x=1+4t; y=1-3t; t?Z: c) The equation30x+47y=-11.Clearly(30;47)=1(47is prime) so there are solu- tions. We find a particular solution by applying the Euclidean algorithm followed by back substitution. Indeed,
47=30?1+17;30=17?1+13;17=13?1+4
and
13=4?3+1;4=1?4+0;
in particular, this double-checks that(30;47)=1; we continue =30?4-17?7=30?4-(47-30)?7=30?11-47?7: Thusx1=11,y1=-7is a particular solution to30x+47y=1. Thusx0=-11x1=-121, y
0=-11y1=77is a particular solution to the desired equation. Therefore, the general
solution is given by x=-121+47t; y=77-30t; t?Z: d) The equation25x+95y=970.Since(25;95)=5?970there are infinitely many solutions. We divide both sides of the equation by 5 to obtain the equivalent equation
5x+19y=194:
9 Note that(5;19)=1andx1=4,y1=-1is a particular solution to5x+19y=1; then x
0=194x1=776,y0=194y1=-194is a particular solution to our equation. Thus the general
solution is given by x=776+19t; y=-194-5t; t?Z: e) The equation102x+1001y=1.We find(102;1001)by applying the Euclidean algorithm:
1001=102?9+83;102=83?1+19;83=19?4+7
and
19=7?2+5;7=5?1+2;5=2?2+1;
hence(102;1001)=1and the equation has infinitely many solutions. We apply back substi- tution to find a particular solution: =19?3-7?8=19?3-(83-19?4)?8=83?(-8)+19?35 =1001?(-43)+102?422: Thusx0=422,y0=-43is a particular solution. Therefore, the general solution is given by x=422+1001t; y=-43-102t; t?Z: Exercise 6.This problem can be stated as finding a non-negative solution to the Diophan- tine equation63x+7=23y, wherexis the number of plantains in a pile, andyis the number of plantains each traveler receives. Replaceyby-yand rearrange the equation into63x+23y=-7and note that(63;23)=1, hence there are infinitely many solutions. We apply Euclidean algorithm
63=23?2+17;23=17?1+6;17=6?2+5;6=5?1+1
and back substitution
1=6-5=6-(17-6?2)=6?3-17=(23-17)?3-17=
hencex1=-4,y0=11is a particular solution to63x+23y=1. We conclude thatx0=-7x1=
28,y0=-7y1=-77is a particular solution. Thus the general solution is given by
x=28+23t; y=-77-63t; t?Z: Replacing againyby-ywe get the general solution to63x+7=23ygiven by x=28+23t; y=77+63t; t?Z: These values ofx;yare both positive whent≥-1, therefore the number of plantains in the pile could be any integer of the form28+23tfort≥-1. 10
Exercise 30.We will use induction to show that4n≡1+3n(mod 9)for alln?Z≥0.
Basen=0:40=1≡1=1+3?0(mod 9).
Hypothesis: The result holds forn.
Stepn+1: We have
4 n+1=4?4n≡4(1+3n)≡4+12n(mod 9) ≡4+3n≡1+3(n+1) (mod 9); as desired; we used the induction hypothesis in the first congruence. Exercise 36.Note that the smallest power of 2 which is larger than all the exponents in this exercise is28=256. Therefore, we will repeatedly square and reduce modulo 47 to compute 2 2
1=2≡2(mod 47)
2
2=4≡4(mod 47)
2
4=16≡16(mod 47)
2
8=256≡21(mod 47)
2
16≡212≡18(mod 47)
2
32≡182≡42(mod 47)
2
64≡422≡25(mod 47)
2
128≡252≡14(mod 47):
a) Compute232:We have seen above that232≡42(mod 47) b) Compute247:Since47=32+8+4+2+1, we have 2
47=23228242221≡42?21?16?4?2≡2(mod 47):
c) Compute2200:Since200=128+64+8, we have 2
200=212826428≡14?25?21≡18(mod 47):
1
Section 4.2
Exercise 2.We will apply the theorem from class that fully describes the solutions of linear congruences. a) Solve3x≡2(mod 7).Since(3;7)=1there is exactly one solution mod7. Since
3?3=9≡2(mod 7)we conclude thatx≡3(mod 7)is the unique solution of the congruences.
b) Solve6x≡3(mod 9).Since(6;9)=3there are exactly three non-congruent solutions mod9. Note thatx0≡2(mod 9)is a particular solution; thenx≡2-(9?3)t=2-3twith the solutionsx≡2;8;5(mod 9). c) Solve17x≡14(mod 21).Since(17;21)=1there is exactly one solution. We know that the solution will correspond to thex-coordinate of a particular solution of the Diophantine equation17x-21y=14. We compute it by applying the Euclidean algorithm and back substitution:
21=17?1+4;17=4?4+1;4=4?1+0
and
1=17-4?4=17-(21-17)?4=17?5-21?4;
hencex1=5,y1=4is a solution to17x-21y=1. Therefore,x0=14x1=14?5=70, y
0=14y1=14?4=56is a particular solution to17x-21y=14. It follows thatx≡x0≡7
(mod 21)is the unique solution to the congruence. congruence. Exercise 6.The congruence12x≡c(mod 30)has solutions if and only if(12;30)=6 non-congruent solutions. Exercise 8.Since 13 is a small number we can solve this exercise by trial and error. a)Since7?2=14≡1(mod 13)we have2-1≡7(mod 13). b)Since9?3=27≡1(mod 13)we have3-1≡9(mod 13). c)Since8?5=40≡1(mod 13)we have5-1≡8(mod 13). d)Since6?11=66≡1(mod 13)we have11-1≡6(mod 13).
Exercise 10.
a)An integerawill have an inverse mod14if and only ifax≡1(mod 14)has a solution, condition are{1;3;5;9;11;13}. b)Note that the inverse ofa-1isaso the inverse ofa?{1;3;5;9;11;13}must also belong to this list since it contains all the invertible elements mod 14. Finally, note that
1?1≡1;3?5=15≡1;9?11=99≡1;13?13=169≡1(mod 14)
which means that 1 -1≡1;3-1≡5;5-1≡3(mod 14) 2 and 9 -1≡11;11-1≡9;13-1≡13(mod 14):
Section 4.3
Exercise 2.The question is equivalent to find a solution to the congruences x≡1(mod 2); x≡1(mod 5); x≡0(mod 3): The unique modulo 10 solution of the first two congruences isx≡1(mod 10). Thus the original system is equivalent to x≡1(mod 10); x≡0(mod 3): We rewrite the first congruence as an equality, namelyx=1+10t, wheretis an integer. Inserting this expression forxinto the second congruence, we find that
1+10t≡0(mod 3)?t≡2(mod 3);
which meanst=2+3s, wheresis an integer. Hence any integerx=1+10t=1+10(2+3s)=
21+30swill be a solution to the problem. For example, takings=0we getx=21. In the
language of congruences, we have shown that x≡21(mod 30); is the unique solution mod 30. We now solve this exercise by applying the CRT to the congruences x≡1(mod 10); x≡0(mod 3): Indeed, we haveb1=1,b2=0,n1=10,n2=3,M=n1n2=30,M1=M?n1=3and M
2=M?n2=10; the formula for the unique solution moduloMgives
[PDF] file - -ORCA