Modular Arithmatic and Number Theory Flashcards
The sum of any rational number and any irrational number is..?
Irrational
What does n | d mean, and how can you rewrite it?
n divides d
d = kn | k ∈ ℤ
floor(-2.5)
-3
ceiling(-2.5)
-2
What is the Quotient-Remainder Theorem?
Given any integer n and a positive integer d, there exists unique integer q and r such that:
n=dq+r and 0 ≤ r < d
q = quotient, r = remainder
Also q = floor(n/d)
Definition:
Odd and Even Integers
Odd: 2k + 1
Even: 2k
(k ∈ ℤ)
If a ≡ b (mod d) and m ≡ n (mod d) then..?
If a ≡ b (mod d) and m ≡ n (mod d) then:
a + m ≡ b + n (mod d) and am ≡ bn (mod d)
Find gcd(192,132)
192 = 132 * 1 + 60
132 = 60 * 2 +12
60 = 12 * 5 = 0
Thus gcd(192,132) = 12
Find gcd(192,132) via Euclidean Algorithm.
gcd(a,b) = gcd(b,r)
Then gcd(b,r) moves to LHS.
Repeat till r = 0
gcd(192,132) = gcd(132,60)
gcd(132,60) = gcd(60,12)
gcd(60,12) = gcd(12,0)
Thus gcd(192,132) = 12
Sequences:
What are they?
Finite, or Infinite?
An ordered list of elements.
Can be finite or infinite.
Define the Well-ordering Principle for the Integers
Let S be a non-empty set of integers, each of which is greater than some fixed integer.
Then S has a smallest element.
Dfference between stong and normal induction?
The key difference between standard induction and strong induction is in the inductive step. In standard induction, we assume the statement is true for some k and then prove it for k+1. In strong induction, we assume the statement is true for all numbers up to k and then prove it for k+1.
Strong induction is particularly useful when the proof for a given value depends on multiple preceding values, not just the immediately preceding one.
Define Mathmatical Induction.
Mathematical induction is a method of mathematical proof typically used to establish a given statement for all natural numbers. It is a form of direct proof, and it has two steps:
Base Step (or Base Case):
This step involves proving the statement for the smallest possible value (usually n=1 for natural numbers, but it can be another value depending on the problem).
Inductive Step:
This step involves assuming the statement is true for some arbitrary natural number k and then proving it is true for k+1. The idea is to show that if the statement holds for one number, it must also hold for the next number.
If both steps are successfully completed, then by the principle of mathematical induction, the statement is true for all natural numbers starting from the base case.
What is an Explicit Formula?
Explicit formulas are where each an is defined without reference to any other term in the sequence, i.e. aₘ = 3ᵐ or aₘ = 2(m-1) etc.
What is a Recursive Definition?
Recursive definitions have base case/s and then a definition for for terms which is dependent on preceding terms, i.e. aₘ = 2aₘ₋₁
