Numbers that appear to the Left of a given number are Less Than (
Zero is both a whole number and an even integer, but it is neither positive nor negative all factors of 12 since they all divide evenly into 12
Rational Numbers These are any numbers that can be expressed as a fraction, which includes all integers and most decimals Examples include - 1 2 , 208,
The integers are represented on the number line as follows : Fig 3 1 • All the positive integers lie to the right of 0 and the negative integers
Everyone has taken at least one class Or Everyone except one student in your class has an inter- universe of discourse is the set of all integers
The second digit can be any digit except equal to the first one, so it has 9 choices too There are 9 · 9 = 81 choices total Page 2 3-digit integers:
Q16 A monotonic integer is made of digits 1, 2, , 9, such that each subsequent digit is All of the following could be a possible value of v EXCEPT
A positive integer that is divisible by exactly two positive numbers, 1 and itself The result of adding all numbers and then dividing by the number of
Two quantifiers are nested if one is within the scope of the other Example: x y (x + y = 0) For every real numbers x and y, if x is positive and y
integers, maintaining all the fundamental laws of arithmetic multiplicative identity, meaning that a×1 = a for all integers a, but integer
fractions, but they can describe how many cows are in a field as well as which includes all integers and most decimals Examples include - 1 2 , 208, 2 3
1, 2, 3, and 4 are consecutive integers 4, 6, 8, and 10 are consecutive even integers 2008 A way to express a range, but the point is not included 1 < x < 3 is the The result of adding all numbers and then dividing by the number of items
(ii) if ab then abc for all integers c, and (iii) if ab and Memorize: An integer p > 1 is called prime if its only positive divisors are 1 and itself one) But there is
integers, maintaining all the fundamental laws of arithmetic Negative numbers multiplicative identity, meaning that a×1 = a for all integers a, but integer
Sanjay has chatted with everyone except Joseph Everyone except one student in your class has an inter- universe of discourse is the set of all integers a
PDF document for free
- PDF document for free
![[PDF] Divisibility Memorize: If a and b are integers, we say that a divides b](https://pdfprof.com/EN_PDFV2/Docs/PDF_6/7004_6integers.pdf.jpg "[PDF] Divisibility Memorize: If a and b are integers, we say that a divides b")
7004_6integers.pdf
Divisibility
Memorize:Ifaandbare integers, we say thatadividesb, and writea|b, if there is an integerksuch thatak=b.
Fact D1. Leta,bandc
be integers. Then (i) ifa|banda|c, thena|(b+c), (ii) ifa|bthena|bcfor all integersc, and (iii) ifa|bandb| cthena|c. You should know how to prove these, and other simple facts about divisibility. The Division Algorithm.Ifaandbare integers andb>0, then there exist unique integersqandrso thata=bq +rand 0≤r
Prime Numbers Memorize:An integerp>1 is calledprimeif its only positive divisors are 1 and itself. An integern>1 which is not prime is calledcomposite. Fundamental Theorem of Arithmetic. Every positive integer can be written as a product of primes in exactly one way, up to the order of the factors. Fact P1.Ifnis composite, thennhas a (prime) divisor which is between 2 and⎷n. You should know how to prove the above fact, and also its implications for the Seive of Eratosthenes.
Seive of Eratosthenes. This generates all of the prime numbers less than or equal to n. Start by writing the numbers 2,3,4,...,nin a line. Then keep repeating the following process until all numbers less than or equal to⎷nhave been crossed out or circled: REPEAT: Circle the next number which is neither circled nor crossed out, and cross out all other multiples of that number which are in the list (some of these are probably already crossed out). The numbers which are not crossed out when the process terminates are all of the primes between 2 andn. You should be able to explain why. Thegcdand thelcm
1 Memorize:Ifaandbare integers which are not both zero, thegreatest common divisor ofaandbis the largest integerdsuch thatd|aandd|b. It is denoted bygcd(a,b). Memorize:Integersaandbare calledrelatively primeifgcd(a,b)=1. Memorize:Theleast common multipleofaandbis the smallest integermsuch thata|m andb|m. It is denoted bylcm(a,b). If you know the prime factorizations of the integersaandb, then it is easy to findgcd(a,b) andlcm(a,b). Suppose a=p e 1 1 p e 2 2 ...p e k k , where eache i ≥0, and b=p f 1 1 p f 2 2 ...p f k k , where eachf i ≥0. (Notice that the same primes appear in both factorizations, although the exponent may be zero.) Then, gcd(a,b)=p min{e 1 ,f 1 } 1 p min{e 2 ,f 2 } 2 ...p min{e k ,f k } k , and lcm(a,b)=p max{e 1 ,f 1 } 1 p max{e 2 ,f 2 } 2 ...p max{e k ,f k } k . The two equations above implygcd(a,b)×lcm(a,b)=ab. Thus, for example, if you know gcd(a,b), you can findlcm(a,b)by division. The reason that the above formulae work comes from Fact D1 (iii) and the Fundamental Theorem of Arithmetic (FTA). Let"s look at thegcd, thelcmis similar. By Fact D1 (iii) any prime divisor of thegcdis a divisor of each number, and by the FTA the only primes that divide a number are those that appear in the prime factorization (with a positive exponent). By the FTA again, the highest power ofp i that divides bothaandbis the minimum ofe i andf i . Thus the largest common divisor ofaandbis the product of these prime powers. You should be able to prove the following facts. The second fact below is the underlying reason that the Euclidean Algorithm (for findinggcd(a,b)) works. Fact G1. Supposex,y, andzare integers. Ifx+y=zand the integerddivides any two ofx,y, andz, then it also divides the third. Fact G2.Ifaandbare integers and we use the division algorithm to writea=bq+r, thengcd(a,b)=gcd(b,r). The Euclidean Algorithm. (Given positive integersaandb, findgcd(a,b)). Suppose a≥b. Use the division algorithm to writea=bq+r,0≤rNumbers in Other Bases The number one hundred and forty-three is usually denoted (in base 10) by 143. What this really stands for is 1×10 2 +4×10 1 +3×10 0 . Its an example of ourplace-valuesystem. There is a ones place, a tens place a hundreds place, etc. More generally, if eachd i stands for a digit, thend k d k-1 ...d 1 d 0 is really a shorthand ford k ×10
k +d k-1 ×10
k-1 +...+ d 1 ×10
1 +d 0 ×10
0 . In base ten we use the digits 0,1,...,9 (from zero up to the base minus one). But there is no real reason to use ten as the base.Memorize:Ifb>1 is an integer and eachd i is an integer between 0 andb-1, then the notation (d k d k-1 ...d 1 d 0 ) b meansd k ×b k +d k-1 × b k-1 +...+d 1 ×b 1 +d 0 ×b 0 .Ifn=d k ×b k +d k-1 ×b k-1 +...+d 1 ×b 1 +d 0 ×b 0 , then (d k d k-1 ...d 1 d 0 ) b is called thebasebrepresentation ofn. If the base is bigger than 10, then we need to use other symbols to represent the digits. For example, in hexadecimal (base 16), the letters A, B, C, D, E, and F stand for 10 through 15, respectively.
Theorem.Ifb>1, then every integernhas a unique basebrepresentation. The digits of the basebrepresentation ofn,from right to left, are the remainders on successive division byb. That is, ifn=bq 0 +r 0 ,0≤rModular Arithmetic Memorize:Ifa,b, andmare integers, we say thatais congruent tobmodulom, and writea≡b(modm)ifm|a-b. You should know how to prove the following facts.
Fact M1.a≡b(modm)?a=b+km, for some integerk.
Fact M2. Supposea≡b(modm) andc≡d(modm.) Then, (i)a+c≡b+d(modm) (ii)a-c≡b-d(modm) (iii)ac≡bd(modm.) The universe of integers (modm) really only consists of the numbers 0,1,2,...,m-1; modulom, any other integer is just one of these with another name. An important implication of Fact M2 is that, when doing calculations (modm,) you can replace any number by another to which it is congruent, and nothing changes. You can think of the integers (modm) as the hours on a circular clock withmhours. Addition corresponds to moving clockwise around the circle an appropriate number of places, subtraction corresponds to moving counter-clockwise. The important part is that the number of times you go around the circle and return to your starting point makes no difference to where you end up. What does matter is the number of places you move when it is no longer possible to make it around the circle any more, and this number is one of 0,1,2,...,m-1.
By Fact M2 (iii), ifa≡b(modm) andcis an integer, thenac≡bc(modm.) You should be able to give an example to show that the converse of this statement is False. You should also be able to use Fact G4 (above) to prove the following statement, which says that we can cancel when the number being cancelled is relatively prime to the modulus. Fact M3.Ifac≡bc(modm) andgcd(c,m)= 1 thena≡b(modm.) In many programming languages there is a functionmod.Ifm?= 0 is an integer, then a(modm) is the unique number among 0,1,2,...,m-1 to whichais congruent modulo m. It is the remainder (as in the division algorithm - that"s why its unique) whenais divided bym. It is easy to use congruences to prove the (familiar) rule that an integer is divisible by 3 if and only if the sum of its decimal digits is divisible by 3. The key is to observe that 4 10≡1(mod 3) and so by Fact M2 (iii) you can change 10 to 1 wherever it occurs. Suppose
n=(d k d k-1 ...d 1 d 0 ) 10 . Thenn≡0(mod 3)?d k ×10
k +d k-1 ×10
k-1 +...+d 1 ×10
1 + d 0 ×10
0 ≡0(mod 3)?d k ×1 k +d k-1 ×1 k-1 +...+d 1 ×1 1 +d 0 ×1 0 ≡0(mod 3) which is what we wanted. A similar argument shows that an integer is divisible by 9 if and only if the sum of its decimal digits is divisible by 9, and only a small change is needed to show that (d k d k-1 ...d 1 d 0 ) 10 is divisible by 11 if and only ifd k -d k-1 +d k-2 -···±d 0 is divisible by 11. It is a good exercise to work through these for yourself. 5
Integers Documents PDF, PPT , Doc