Kayhan Erciyeş writes in the 6th Chapter of his book, "Discrete Mathematics and Graph Theory", the following about Introduction to Number Theory:
I collected the answers to the most substantial questions regarding this chapter:
Division of Two Integers
Division is the arithmetic operation whereby the amount of times one number (the divisor) is contained within another number (the dividend) is calculated. For integers, this often results in a quotient and possibly a remainder.
Example: 8 divided by 3 equals 2 with a remainder of 2.
"a divides b"
This means that when b is divided by a, the remainder is 0. In other words, a is a divisor of b, and b is a multiple of a.
Example: 3 divides 6 because 6 / 3 = 2 with no remainder.
Greatest Common Divisor (GCD)
The greatest common divisor of two integers a and b is the largest positive integer that divides both a and b without leaving a remainder. Example: GCD of 54 and 24 is 6.
Properties of the Greatest Common Divisor
Commutativity: GCD(a, b) = GCD(b, a).
Uniqueness: There is exactly one GCD for any pair of integers (excluding zero).
Associativity: GCD(a, GCD(b, c)) = GCD(GCD(a, b), c).
Linear Combination: GCD(a, b) can always be expressed as an integer linear combination of a and b, i.e., GCD(a, b) = ax + by for some integers x and y.
Euclid’s Algorithm for GCD
If b = 0, then GCD(a, b) is a.
Otherwise, calculate GCD(b, a mod b) where "mod" denotes the modulus operation.
Repeat step 2 until the remainder is 0. The non-zero remainder at this final step is the GCD of a and b.
Maple code:
gcd := proc(a::nonnegint, b::nonnegint)
description "returns the greatest common divisor of a and b";
if b = 0 then
return a;
end if;
if a mod p = 0 then
return b;
end if;
return gcd2(b, a mod b);
end procLeast Common Multiple (LCM):
The least common multiple of two integers a and b is the smallest positive integer that is divisible by both a and b without leaving a remainder. Example: LCM of 4 and 6 is 12.
Properties of the Least Common Multiple:
Commutativity: LCM(a, b) = LCM(b, a).
Associativity: LCM(a, LCM(b, c)) = LCM(LCM(a, b), c).
Relationship with GCD: LCM(a, b) * GCD(a, b) = |a*b|.
Prime Number
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. Example: 7 is a prime number because it is only divisible by 1 and 7.
Fundamental Theorem of Arithmetic
This theorem states that every integer greater than 1 is either a prime number or can be uniquely represented as a product of prime numbers, up to the order of the factors.
Method of Eratosthenes
List all the numbers from 2 to n.
Starting with the first prime number (2), remove all of its multiples from the list.
Move to the next number in the list and repeat the process until you have processed all numbers up to n.
The remaining numbers in the list are the primes up to n.
Algorithm to Find Primes up to n
This can refer to the Sieve of Eratosthenes (described above) or other sieves like the Sieve of Atkin, which are efficient methods for finding all prime numbers up to a specified integer n.
Congruence of Two Integers
Two integers a and b are said to be congruent modulo n if their difference a - b is divisible by n. This is denoted as a ≡ b (mod n). Example: 17 ≡ 5 (mod 6) because 17 - 5 = 12 is divisible by 6.
Diffie-Hellman Protocol
A method of securely exchanging cryptographic keys over a public channel. Two parties agree on a large prime number and a base. Then, they each select a private key, produce a public key by raising the base to the power of their private key modulo the prime number, and exchange public keys. Each party can then compute the shared secret by raising the other's public key to the power of their private key modulo the prime number.
RSA Protocol
An asymmetric cryptographic algorithm based on the practical difficulty of factoring the product of two large prime numbers. It involves choosing two large primes, calculating their product (n) and a totient, choosing an encryption key, and then computing a decryption key.
Yorumlar