need in 12hours

1

Summer, 2015 Math 4400 Meeting #12 Update of

Some Definitions, Shorthand Notations, Theorems, and Notes

A. Note the following shorthand notations:

i. Given p, q 0 {statements}, “p Y q” is read “p implies q”

ii. Given p, q 0 {statements}, “p ] q” is read “p implies q and p is implied by q.” or, in other words, “q is true if and only if p is true.”

iii. “�” is read “there exist.”

iv. “h” is read “such that”

v. “ò” is read “there does not exist.”

vi. “�!” is read “there exist uniquely.”

vii. “�” is read “for all.”

B. Note some shorthand notations and definitions from the language of set theory:

i. Note that “x 0 A” is read “x is an element of set A.”

Also note the following:

Given n is a natural number, “x1, x2, x3, ..., xn 0 A” is read “x1, x2, x3, and so on through xn are elements of set A.”

Further note the meaning of “ó” as well as the use of “/” through any relationship sign.

ii. Note: “V” is a symbol for the universe.

Definition for the universe:

Given a specific domain, V = {elements in the domain}

iii. Note: “i” is a symbol for the empty set.

Definition of the empty set:

i 0 {sets} h (ò x 0 V h x 0 i)

2

iv. Given A, B 0 {sets}, note that “A f B” is read “A is a subset of B.”

Definition for subset:

Given A, B 0 {sets}, (A f B ] (x 0 A Yx 0 B))

v. Definition for equal sets:

Given A, B 0 {sets}, (A = B ] ( A f B and B f A))

vi. Given A, B 0 {sets}, note that “A c B” is read “the union of A and B.”

Definition for union of sets:

Given A, B 0 {sets}, (A c B = {x : x 0 A or x 0 B} )

vii. Given A, B 0 {sets}, note that “A 1 B” is read “the intersection of A and B.”

Definition for intersection of sets:

Given A, B 0 {sets}, (A 1 B = {x : x 0 A and x 0 B})

viii. Given A, B 0 {sets}, note that “A - B” is read “A without B.”

Definition for without:

Given A, B 0 {sets}, (A - B = {x : x 0 A and x ó B})

C Note the following shorthand conventions for naming subsets of numbers along with some definitions:

i. “Z” is read “the set of all integers.”

Thus, Z = {..., G3, G2, G1, 0, 1, 2, 3, ...}

ii. “ù” is read “the set of all natural numbers” or “the set of positive integers.”

Thus, ù = {1, 2, 3, ... }

iii. “�” is read “the set of all primes.”

Sidebar note: The definition for “d * p” that’s used in the definition for � is given in Item #E-iv in this document.

Here is a definition for �:

� = { p 0 ù - { 1 } : d * p Y d 0 { Gp, G1, 1, p }}

3

iv. Here is a definition for composite number:

{ composite numbers } = ù – ( � c { 1 } )

v. “ù” is read “the set of all whole numbers” or “the set of non-negative integers.”

Thus, ù = {0, 1, 2, 3, ...}

vi. “ú” is read “the set of all real numbers.”

vii. “Q” is read “the set of all rational numbers.”

Here is a definition for rational number:

Q = {q : � n, d 0 Z h = q}

Sidebar definitions from philosophy:

A. Definition for ontology:

Ontology is the branch of philosophy focusing on questions about existence and truth (i.e., what truly exists).

B. Definition for epistemology:

Epistemology is the branch of philosophy involving theories of knowledge, thus focusing on the following questions: What is knowledge? How is knowledge acquired? How do we determine truth? How do we know what we know?

C. Definition for axiology:

Axiology is the branch of philosophy involving theories of ethics, thus focusing on questions about the value of behaviors.

D. Definition for aesthetics:

Aesthetics is the branch of philosophy (sometimes perceived as a sub- branch of axiology) involving theories of beauty (i.e., sensory values or taste)

4

Sidebar Definitions of inductive and deductive reasoning:

i. Inductive reasoning is the cognitive process by which people formulate generalizations (e.g., propose a conjecture) based on patterns gleaned from a finite string of specific examples or experiences.

ii. Deductive reasoning is the cognitive process by which people determine whether or not a specific example is subsumed by an accepted generalization. Aristotlean syllogism is the paradigm for logical deductions: ( major premise v minor premise ) Y conclusion

D. Note the following four definitions from the world of real number mathematics (e.g., calculus):

i. Here is the definition of a subset of ú having a lower bound:

Given A f ú, ( A has a lower bound ] � x 0 ú h x # y � y 0 A )

ii. Here is the definition of a subset of ú having an upper bound:

Given A f ú, ( A has an upper bound ] � x 0 ú h y # x � y 0 A )

iii. Here is the definition of a subset of ú having a least element:

Given A f ú, ( A has a least element ] � x 0 A h x # y � y 0 A )

iv. Here is the definition of a subset of ú having a greatest element:

Given A f ú, ( A has a greatest element ] � x 0 A h y # x � y 0 A )

E. Note the following list of definitions, shorthand notations, axioms, and theorems that we’ve developed specifically for our work wirh number theory (up through Theorem 11 (out of 25 theorems):

i. Here is Axiom 1:

Z is closed under + (i.e., a, b 0 Z Y a + b 0 Z )

ii. Here is Axiom 2 (i.e., the least integer principle and the greatest integer principle):

The Least Integer Principle: Every nonempty subset of integers that has a lower bound contains a least element.

The Greatest Integer Principle: Every nonempty subset of integers that has an upper bound contains a greatest element.

5

iii. Here is Theorem 0 (the Principle of Mathematical Induction):

( p : ù 6 { true, false } h (( either p(n) is a true proposition or p(n) is a false proposition) and p(1) is true and ( p(k) is true Y p(k + 1) is true ))) Y p(n) is true � n 0 ù

iv. Given a, b 0 Z, “a*b” is read “a is a divisor of b” or “b is a multiple of a.”

Here is a definition for the relation of is a divisor or is a multiple:

Given a, b 0 Z, (a*b ] � i 0 Z h ai = b)

v. Here is a definition for proper divisor:

Given n 0 ù, ( { proper divisors of n } = { d : d 0 ù - { n } and d * n })

vi. Here is Theorem 1:

( a*b and b*c) Y a*c

vii. Here is Theorem 2:

� c1, c2, ..., cn 0 Z

viii. Here is Theorem 3 (the Division Algorithm):

( a 0 Z and b 0 ù) Y (�!(q, r) h q, r 0 Z and a = qb + r and 0 # r < b)

ix. Note that depending on context and given that a, b 0 Z, “(a, b) = d ” is read “d is

the greatest common divisor of a and b.

Here is a definition for greatest common divisor of a pair of integers:

Given a, b 0 Z, ((a, b) = d ] (d*a, d*b, and ((e*a and e*b) Y e # d )))

x. Note that if ( a, b ) = 1 for some a, b 0 Z, then a and b are a relatively prime pair.

xi. Here is Theorem 4:

(a, b) = d Y = 1

6

xii. Here is Theorem 5:

� a, b, q, r 0 Z, (a = bq + r Y (a, b) = (b, r))

xiii. Note the following definition of perfect number:

p 0 {perfect numbers} ] p = where (*{d1, d2, d3, ..., dk}* = k and

{d1, d2, d3, ..., dk} = {proper divisors of p})

xiv. Note the following definition of Mersenne number:

{2n - 1: n 0 ù } = {Mersenne numbers}

xv. Note Euclid’s formula for generating perfect numbers:

2n!1 0 V Y 2n-1 (2n!1) 0 {perfect numbers}

xvi. Note other gems from your reading of Hoffman’s Archimedes’ Revenge (e.g., polygonal numbers, “biblically significant numbers,” and lots of other stuff listed in the reading outlines)

xvii. Here is Theorem 6 (the Euclidean Algorithm):

If a, b 0 ù such that:

a = q1b + r1 such that 0 # r1 < b,

b = q2r1 + r2 such that 0 # r2 < r1,

r1 = q3r2 + r3 such that 0 # r3 < r2,

• • •

rk = rk+1qk+2 + rk+2 such that 0 # rk+2 < rk+1,

then for k large enough, say k = t, we have

rt-1 = rtqt+1 + 0 and

(a, b) = rt.

7

xviii. Here is Theorem 7:

(a, b) = d) Y (� x, y 0 Z h ax + by = d)

xix. Here is Theorem 8:

(d*ab and (d, a) =1) Y (d*b)

xx. Here is Theorem 9:

(n 0 ù and n > 1) Y � p 0 � h p*n

xxi. Here is Theorem 10:

(n 0 ù-{1}) Y (� p1, p2, p3, ..., pk 0 � h = n)

xxii. Here is Theorem 11:

� is infinite.

xxiii. Here is Theorem 12:

c 0 {composites} Y � d 0 ù - {1} h d # and d*c

xxiv. Here is Theorem 13:

c 0 {composites} Y � p 0 V h p # and p*c

xxv. Here is Theorem 14:

(p 0 � and a, b 0 Z h p*ab) Y (p*a or p*b)

xxvi. Here is Theorem 15:

p 0 � h p* Y (p*ai for some i 0 {1, 2, 3, ..., k})

xxvii. Here is Theorem 16:

(p, q1, q2, q3, ..., qn 0 �h p* ) Y p = qk for some k 0 {1, 2, 3, ..., n}

xxviii. Here is Theorem 17 (the Fundamental Theorem of Arithmetic):

n 0 ù - { 1} Y ( n can be written as a product of primes in one and only one way (Note: Order is not considered a difference)

8

F. Note the following list of definitions and shorthand notations that we’ve comprehended specifically for our work with cryptography

i. Note:

Given a, b, m 0 Z h m $ 1, “a / b (mod m)” is read “a is congruent to b

modulo m” or “a is congruent to b mod m.”

ii. Here is a definition for congruence among integers:

Given a, b, m 0 Z h m $ 1, ( a / b (mod m) ] m * a - b )

iii. Note:

Given m 0 ù and a 0 Z, “[a]m” is read “the congruence class of a modulo m.”

iv. Here is a definition for congruence class:

Given m 0 ù and a 0 Z, ( [a]m = { x : x / a (mod m)})

v. Note:

Given m 0 ù and a, b 0 Z, “[a]m r [b]m” is read

“the sum of the classes [a]m and [b]m .”

vi. Here is a definition for sum of congruence classes:

Given m 0 ù and a, b 0 Z, ( [a]m r [b]m = [a + b]m )

vii. Note:

Given m 0 ù and a, b 0 Z, “[a]m u [b]m” is read

“the product of the classes [a]m and [b]m .”

viii. Here is a definition for product of congruence classes:

Given m 0 ù and a, b 0 Z, ( [a]m u [b]m = [ab]m )

G. Note the following list of definitions, shorthand notations, axioms, and theorems that we’ve developed specifically for our work in number theorem (completing our list of 25 theorems):

9

i. Here is Theorem 18:

( a, b, c 0 Z, m 0 ù, ( c, m ) = 1, and ac / bc (mod m)) Y a / b (mod m)

ii. Here is Theorem 19:

( p 0 �, r 0 ù, and r < p ) Y p*

iii. Here is Theorem 20 (Fermat’s Little Theorem):

( a 0 ù, p 0 �, and p ð a ) Y

x. Here is Theorem 21:

((x0, y0 ) is a solution of the linear Diophantine equation ax + by = c) Y ((x0 + bt, y0 - at) is also a solution for any integer t).

xi. Here is Theorem 22:

(a, b)ðc Y the linear Diophantine equation ax + by = c has no solutions.

xii. Here is Theorem 23:

(a, b)*c Y the linear Diophantine equation ax + by = c has a solution.

xiii. Here is Theorem 24:

((a, b) = 1 and (x0, y0) 0 {(x, y) : ax + by = c} Y

(all solutions of ax + by = c are given by x = x0 + bt, y = y0 - at where t 0 Z )

In other words: ((a, b) = 1 and (x0, y0) 0 {(x, y) : ax + by = c}) Y

{(x, y) : ax + by = c} = {(x, y) : x = x0 + bt, y = y0 - at where t 0 Z }

xiv. Here is Theorem 25:

( (a, b)*c ) Y ( The solutions for linear Diophantine equation ax + by = c are as follows:

x = x0 + , y = y0 - where (x0, y0) is any solution and t 0 Z

In other words: ( (a, b)*c ) Y {(x, y) : ax + by = c} =

{(x, y) : x = x0 + , y = y0 - where t 0 Z })