  # Introduction to Number Theory

Lecture Outline

What we’ve covered so far:

– symmetric encryption

– hash functions

number theory

– public-key encryption

digital signatures

• Introduction to number theory

– divisibility

– GCD and Euclidean algorithm

– prime and composite numbers

– Chinese remainder theorem

– Euler Ø function

– Fermat’s theorem

Divisibility

• Divisibility

– given integers a and b, we say that b divides a (denoted by b|a) if b/a
is a whole number (or b = ac for an integer c)

– b is called a divisor of a

• Transitivity theorem

– we are given integers a, b, and c, where all of them > 1

– if a|b and b|c, then a|c

– proof

Linear combination theorem

– let a, b, c, x, and y be integers > 1

– if a|b and a|c, then a|(bx+cy)

• Proof

– a|b=>

– a|c =>

Division algorithm (theorem)

– let a > 0 and b be two integers

– then there exist two unique integers q and r such that 0 ≤ r < a and
b = aq +r

to show existence:

uniqueness can be shown by contradiction:

• assume there are integers q' and r' such that b = aq' +r' and
0 ≤ r' < a

• Notation

– the integer q is called the quotient

– the integer r is called the remainder

– [x] is the floor of x (largest integer ≤ x)

– [x] is the ceiling of x (smallest integer ≥ x)

– then q = [b/a] and r = b mod a

Greatest Greatest Divisor

Greatest common divisor (GCD)

– suppose we are given integers a and b which are not both 0

– their greatest common divisor gcd(a, b) = c is the greatest number
that divides both a and b

– example: gcd(128, 100) = 4

– it is clear that gcd(a, b) = gcd(b, a)

GCD and multiplication

– we are given integers a, b, and m > 1

– if gcd(a,m) = gcd(b,m) = 1, then gcd(ab,m) = 1

– example: gcd(25, 7) = gcd(3, 7) = 1 => gcd(75, 7) = 1

• GCD and division

– Theorem 1

• we are given integers a and b

• if g = gcd(a, b), then • example: – Theorem 2

• if a is a positive integer and b, q, and r are integers with
b = aq +r, then gcd(b, a) = gcd(a, r)

• we can use this theorem to find GCD

Euclidean Algorithm

• Fact: given integers a > 0, b, q, and r such that b = aq +r,
gcd(a, b) = gcd(a, r)

• Euclidean algorithm for finding gcd(a, b)

– apply the division algorithm iteratively to compute the remainder

– the last non- zero remainder is the answer

– while a ≠ 0 do
r b mod a
b a
a r
return b

• Example:

– compute GCD of 165 and 285

steps of Euclidean algorithm:

– the answer is gcd(165, 285) =

Towards Extended Towards Extended Euclidean Algorithm

• Theorem:

– if integers a and b are not both 0, then there are integers x and y so
that ax +by = gcd(a, b)

– we can find x and y using the extended Euclidean algorithm

• Example:

– find x and y such that 285x +165y = gcd(285, 165) = 15

– we start with the next to last equation in our example and work
backwards

 Prev Next

Start solving your Algebra Problems in next 5 minutes!      2Checkout.com is an authorized reseller
of goods provided by Sofmath

Attention: We are currently running a special promotional offer for Algebra-Answer.com visitors -- if you order Algebra Helper by midnight of January 21st you will pay only \$39.99 instead of our regular price of \$74.99 -- this is \$35 in savings ! In order to take advantage of this offer, you need to order by clicking on one of the buttons on the left, not through our regular order page.

If you order now you will also receive 30 minute live session from tutor.com for a 1\$!

You Will Learn Algebra Better - Guaranteed!

Just take a look how incredibly simple Algebra Helper is:

Step 1 : Enter your homework problem in an easy WYSIWYG (What you see is what you get) algebra editor: Step 2 : Let Algebra Helper solve it: Step 3 : Ask for an explanation for the steps you don't understand: Algebra Helper can solve problems in all the following areas:

• simplification of algebraic expressions (operations with polynomials (simplifying, degree, synthetic division...), exponential expressions, fractions and roots (radicals), absolute values)
• factoring and expanding expressions
• finding LCM and GCF
• (simplifying, rationalizing complex denominators...)
• solving linear, quadratic and many other equations and inequalities (including basic logarithmic and exponential equations)
• solving a system of two and three linear equations (including Cramer's rule)
• graphing curves (lines, parabolas, hyperbolas, circles, ellipses, equation and inequality solutions)
• graphing general functions
• operations with functions (composition, inverse, range, domain...)
• simplifying logarithms
• basic geometry and trigonometry (similarity, calculating trig functions, right triangle...)
• arithmetic and other pre-algebra topics (ratios, proportions, measurements...)

ORDER NOW!         