Advanced High-School Mathematics
SECTION 2.1 Elementary Number Theory 71 Applying the Euclidean algorithm yields 855 = 6·138 + 27 138 = 5·27 + 3 27 = 9·3 + 0, an ...
72 CHAPTER 2 Discrete Mathematics Therefore, d = gcd(1832,2417) = 1; working backwards through the above yields 157 · 1832 − 119 ...
SECTION 2.1 Elementary Number Theory 73 m ≡ 7(mod 30) m ≡ 4(mod 19). In this case, 7· 30 − 11 ·19 = 1 and so 3· 7 · 30 − 3 · 11 ...
74 CHAPTER 2 Discrete Mathematics m ≡ 7(mod 10) m ≡ 17(mod 26). Find the least positive integer solution of the congruences m ...
SECTION 2.1 Elementary Number Theory 75 2.1.4 Primes and the fundamental theorem of arithmetic We have already defined aprimeas ...
76 CHAPTER 2 Discrete Mathematics Therefore the original list of primes did not containallof the primes. This contradiction prov ...
SECTION 2.1 Elementary Number Theory 77 a=pe 11 pe 22 ···perr, b=pf 11 pf 22 ···pfrr be the prime factorization of a and b where ...
78 CHAPTER 2 Discrete Mathematics Show that there exist unique positive integers xandy satisfying x^2 + 84x+ 2008 =y^2. Find th ...
SECTION 2.1 Elementary Number Theory 79 (c) Conclude from part (b) that there must be infinitely many primes. Here’s yet anothe ...
80 CHAPTER 2 Discrete Mathematics of color. The proof rested on the fact that this setCof criminals must have aleast element, wh ...
SECTION 2.1 Elementary Number Theory 81 Therefore every elementn ∈ N is inG, which means that the above statement is true for al ...
82 CHAPTER 2 Discrete Mathematics does give us a convenient language in which to streamline certain argu- ments. Namely, when we ...
SECTION 2.1 Elementary Number Theory 83 Prove the following: (i) 1 + 3 + 5 +···+ (2n−1) =n^2 (n= 1, 2 ,...) (ii) 1^3 + 2^3 + 3^ ...
84 CHAPTER 2 Discrete Mathematics 1 x 1 + 1 x 2 +···+ 1 xn + 1 xn+1 ≥ n^2 1 −xn+1 + 1 xn+1 . Next, you need to argue that becaus ...
SECTION 2.1 Elementary Number Theory 85 Clearly P(1) is true. Assuming that P(n) is true, assume that uandv are positive integer ...
86 CHAPTER 2 Discrete Mathematics a^6 = ∑^6 k=0 Ñ 6 k é (7q)kr^6 −k≡r^6 (mod 7). This reduces matters to only six easily verifia ...
SECTION 2.1 Elementary Number Theory 87 above observation. Note first that it suffices to assume thata≥1; we shall argue by indu ...
88 CHAPTER 2 Discrete Mathematics Let p be a prime number. The integers a and b are said to be multiplicative inverses modulopi ...
SECTION 2.1 Elementary Number Theory 89 (a) Sinceφ(n)< nfor alln, we see that the sequencea 1 , a 2 , ..., eventually becomes ...
90 CHAPTER 2 Discrete Mathematics 18 = 3·5 + 3 5 = 1·3 + 2 3 = 1·2 + 1. Now work backwards and get 2 · 18 − 7 ·5 = 1. This says ...
«
1
2
3
4
5
6
7
8
9
10
»
Free download pdf