Example: Neither 21 and 10 are prime, but they are coprime. d = gcd(a,b) = max(d: d|a d|b) d|a d|b eZ, (e|a e|b) → d ≥ e Example: gcd(24,36)=? Positive common divisors: 1,2,3,4,6,12… Greatest is 12.ĩ GCD shortcut If the prime factorizations are written as and, then the GCD is given by: Example: a=84=2♲♳ The greatest common divisor gcd(a,b) of integers a,b (not both 0) is the largest (most positive) integer d that is a divisor both of a and of b. The symbol that looks like a backwards “set-membership” relational operator is an abbreviation for “such that”. a = dq + r and 0 r 0: !q,rZ: 0r 0) we can find q and r by: q=ad, r=aqd. For any integer dividend a and divisor d≠0, there is a unique integer quotient q and remainder rN s.t. if there exists an integer k such that bka, we say a divides b which is denoted by ab. Really just a theorem, not an algorithm… The name is used here for historical reasons. Basic Number Theory Divisibility Let a,b be integers with a0.
#Basic number theory powerpoint series
Its "Prime Factorization" Every positive integer has a unique representation as the product of a non-decreasing series of zero or more primes. Non-prime integers greater than 1 are called composite, because they can be composed by multiplying two integers greater than 1. The only positive factors of a prime p are 1 and p itself. (a|b b|c) a|c Proof of (2): a|b means there is an s such that b=as, and a|c means that there is a t such that c=at, so b+c = as+at = a(s+t), so a|(b+c) also.■ĥ Prime Numbers An integer p>1 is prime iff it is not the product of any two integers greater than 1: p>1 a,bN: a>1, b>1, ab=p.
If a divides b, then we say a is a factor or a divisor of b, and b is a multiple of a. a|b “a divides b” : “cZ: b=ac” “There is an integer c such that c times a equals b.” Example: 312 True, but 37 False. These basics of the number theory makes a basis for many CS-related algorithms and technologies Also, there are some specific concepts and theorems regarding division. Why do we mention division first? Because addition, subtraction, and multiplication of integers are relatively simple. Vital in many important algorithms today (hash functions, cryptography, digital signatures). Of course you already know what the integers are, and what division is… But: There are some specific notations, terminology, and theorems associated with these concepts which you may not know.
Rosen 5th ed., §§ Now we will jump to mathematical properties of integers, which are the topics of sections 4,5, and 6.
0 kommentar(er)
