30 Questions
What does the notation 'b | a' mean?
b is a divisor of a
Which of the following properties of divisibility is NOT mentioned in the text?
Any b ≠ 0 divides 0
What is the purpose of the example with $b = 7, g = 14, h = 63, m = 3, n = 2$ in the text?
To demonstrate that 7 is a divisor of $3 * 14 + 2 * 63$
What is the meaning of the statement '$13 | 182$' in the text?
13 is a divisor of 182
Which of the following statements about divisibility is NOT mentioned in the text?
If a | b and b | c, then a | (b + c)
What is the significance of the statement '$17 | 0$' in the text?
17 is a divisor of 0
If 24 = 9 (mod n), what is the possible value of n?
3
Given 57 = 6 (mod m), what could be a possible value for m?
7
What is the value of m if 83 = -2 (mod m)?
6
If 90 = 6 (mod p), what are the potential values for p?
20
For which of the following equations does the given congruence hold? 25 = 4 (mod x)
$x = 6$
If $64 = -3$ (mod y), what is a possible value for y?
$11$
What is the relationship between a positive integer a and a nonnegative integer n when divided, according to the Division Algorithm?
a = qn + r, where 0 ≤ r < n
What is the general relationship given in the Division Algorithm?
a = qn + r
What is the Euclidean Algorithm primarily used for in number theory?
Determining the greatest common divisor of two positive integers
When are two integers considered relatively prime?
When their only common positive integer factor is 1
How is the greatest common divisor (GCD) of two numbers defined?
The largest integer that divides both numbers
What does gcd(0,0) equal according to the content provided?
0
What algorithm, developed in 2002, efficiently determines whether a given large number is prime?
AKS algorithm
Who is believed to have discovered the Chinese Remainder Theorem (CRT) around 100 A.D.?
Sun-Tsu
Which theorem provides a way to reconstruct integers in a certain range from their residues modulo a set of pairwise relatively prime moduli?
Chinese Remainder Theorem (CRT)
What property must be known beforehand for the Chinese Remainder Theorem (CRT) to be applied when dealing with potentially very large numbers?
Factorization of M
Which of the following algorithms produces a probabilistic result for proving the primality of very large numbers?
Fermat's Primality Test
What theorem does not appear to be as efficient as the Miller-Rabin algorithm for determining whether a given large number is prime?
AKS algorithm
What is the result of [(11 mod 8) + (15 mod 8)] mod 8?
2
Which property of modular arithmetic is demonstrated by the expression [(11 mod 8) - (15 mod 8)] mod 8?
Additive inverse
What is the result of [(11 mod 8) * (15 mod 8)] mod 8?
5
According to the information provided, what is the unique way that any integer a > 1 can be factored?
a = p1^a1 * p2^a2 * ... * pn^an
What is the result of the Extended Euclidean Algorithm example provided?
d = 1; x = -111; y = 355
Which property of prime numbers is mentioned in the text?
Prime numbers only have divisors of 1 and itself
Study Notes
Divisibility
- A nonzero
bdividesaifa = mbfor somem, wherea,b, andmare integers. -
bdividesaif there is no remainder on division. - Notation
b | ameansbdividesa. - If
b | a, thenbis a divisor ofa. - Example:
1,2,3,4,6,8,12, and24are divisors of24.
Properties of Divisibility
- If
a | 1, thena = ±1. - If
a | bandb | a, thena = ±b. - Any
b ≠ 0divides0. - If
a | bandb | c, thena | c. - If
b | gandb | h, thenb | (mg + nh)for arbitrary integersmandn.
Modular Arithmetic
- Two integers
aandbare congruent modulonif(a mod n) = (b mod n). - Notation
a = b (mod n)meansaandbare congruent modulon. - Example:
73 = 4 (mod 23);21 = -9 (mod 10).
Properties of Congruences
- If
a = b (mod n), thenn | (a - b). - If
a = b (mod n), thenb = a (mod n). - If
a = b (mod n)andb = c (mod n), thena = c (mod n).
Division Algorithm
- Given positive integer
nand nonnegative integera, dividingabyngives quotientqand remainderrsuch thata = qn + r. -
0 ≤ r < n.
Greatest Common Divisor (GCD)
- The GCD of
aandbis the largest integer that divides bothaandb. - Notation
gcd(a, b)represents the GCD ofaandb. -
gcd(a, b)is the largestcsuch thatcdividesaandb. -
gcd(a, b) = max[k, such that k | a and k | b].
Chinese Remainder Theorem (CRT)
- The CRT states that it is possible to reconstruct integers in a certain range from their residues modulo a set of pairwise relatively prime moduli.
- The CRT can be stated in several ways.
- It provides a way to manipulate large numbers modulo
Min terms of tuples of smaller numbers.
Prime Numbers
- Prime numbers only have divisors of
1and themselves. - Prime numbers are central to number theory.
- Any integer
a > 1can be factored in a unique way asa = p1^a1 * p2^a2 * ....
Test your knowledge on Chapter 2 'Introduction to Number Theory' from William Stallings' book 'Cryptography and Network Security Eighth Edition'. Explore concepts like divisibility and divisors in integer numbers.
Make Your Own Quizzes and Flashcards
Convert your notes into interactive study material.
Get started for free
