3Which statement correctly defines a prime number?
Primes
Easy
A.It has exactly two positive divisors.
B.It has no positive divisors.
C.It has exactly three positive divisors.
D.It has exactly one positive divisor.
Correct Answer: It has exactly two positive divisors.
Explanation:
A prime number has exactly two positive divisors: and the number itself.
Incorrect! Try again.
4Which of the following numbers is prime?
Primes
Easy
A.
B.
C.
D.
Correct Answer:
Explanation:
The only positive divisors of are and , so it is prime.
Incorrect! Try again.
5What is ?
Greatest common divisors and least common multiples
Easy
A.
B.
C.
D.
Correct Answer:
Explanation:
The greatest positive integer that divides both and is .
Incorrect! Try again.
6What is ?
Greatest common divisors and least common multiples
Easy
A.
B.
C.
D.
Correct Answer:
Explanation:
The smallest positive multiple shared by and is .
Incorrect! Try again.
7Which equation is the correct first step of the Euclidean algorithm for finding ?
Euclidean algorithm
Easy
A.
B.
C.
D.
Correct Answer:
Explanation:
The Euclidean algorithm begins by dividing by , giving quotient and remainder .
Incorrect! Try again.
8Using the Euclidean algorithm, what is ?
Euclidean algorithm
Easy
A.
B.
C.
D.
Correct Answer:
Explanation:
The divisions give remainders , , and , so the greatest common divisor is .
Incorrect! Try again.
9Which equation expresses as a linear combination of and ?
Bezout's lemma
Easy
A.
B.
C.
D.
Correct Answer:
Explanation:
Because , this is a valid Bezout identity.
Incorrect! Try again.
10If , what does Bezout's lemma guarantee?
Bezout's lemma
Easy
A.There are positives such that .
B.There are integers such that .
C.There are primes such that .
D.There are integers such that .
Correct Answer: There are integers such that .
Explanation:
Bezout's lemma states that the greatest common divisor of and can be written as for some integers and .
Incorrect! Try again.
11Which value of solves ?
Linear congruence
Easy
A.
B.
C.
D.
Correct Answer:
Explanation:
For , , so .
Incorrect! Try again.
12Which pair gives all solutions in to ?
Linear congruence
Easy
A.
B.
C.
D.
Correct Answer:
Explanation:
Both and .
Incorrect! Try again.
13What is the multiplicative inverse of modulo ?
Inverse of a modulo m
Easy
A.
B.
C.
D.
Correct Answer:
Explanation:
Since , the inverse of modulo is .
Incorrect! Try again.
14When does an integer have a multiplicative inverse modulo ?
Inverse of a modulo m
Easy
A.When
B.When divides
C.When
D.When
Correct Answer: When
Explanation:
An inverse of modulo exists exactly when and are relatively prime.
Incorrect! Try again.
15Which number satisfies both and ?
Chinese remainder theorem
Easy
A.
B.
C.
D.
Correct Answer:
Explanation:
The number leaves remainder when divided by and remainder when divided by .
Incorrect! Try again.
16If and are coprime, what does the Chinese remainder theorem say about the system and ?
Chinese remainder theorem
Easy
A.It has no solution unless .
B.It has a unique solution modulo .
C.It has a unique solution modulo .
D.It has exactly two solutions modulo .
Correct Answer: It has a unique solution modulo .
Explanation:
For coprime moduli and , the system has one unique solution modulo their product .
Incorrect! Try again.
17Using a Caesar cipher with a shift of , what is the decryption of KHOOR?
Encryption and decryption by Caesar cipher and affine transformation
Easy
A.KHOOR
B.NKRRU
C.HELLO
D.IFMMP
Correct Answer: HELLO
Explanation:
Decryption shifts each letter backward by : KHOOR becomes HELLO.
Incorrect! Try again.
18In an affine cipher, letters are numbered . Using , which letter encrypts B?
Encryption and decryption by Caesar cipher and affine transformation
Easy
A.I
B.M
C.N
D.P
Correct Answer: N
Explanation:
For B, . Thus , which corresponds to N.
Incorrect! Try again.
19If is prime and does not divide , which congruence is given by Fermat's little theorem?
Fermat's little theorem
Easy
A.
B.
C.
D.
Correct Answer:
Explanation:
Fermat's little theorem states that when is prime and does not divide .
Incorrect! Try again.
20Using Fermat's little theorem, what is ?
Fermat's little theorem
Easy
A.
B.
C.
D.
Correct Answer:
Explanation:
Since is prime and does not divide , Fermat's little theorem gives .
Incorrect! Try again.
21What is the remainder when is divided by ?
Divisibility and modular arithmetic
Medium
A.
B.
C.
D.
Correct Answer:
Explanation:
The powers of modulo repeat as . Since , we get .
Incorrect! Try again.
22Find the least nonnegative residue of modulo .
Divisibility and modular arithmetic
Medium
A.
B.
C.
D.
Correct Answer:
Explanation:
Modulo , , , and . Thus .
Incorrect! Try again.
23Given the prime factorization , how many positive divisors does have?
Primes
Medium
A.
B.
C.
D.
Correct Answer:
Explanation:
The number of positive divisors is .
Incorrect! Try again.
24Which of the following numbers is prime?
Primes
Medium
A.
B.
C.
D.
Correct Answer:
Explanation:
Testing primes up to shows that has no prime divisor. The others factor as , , and .
Incorrect! Try again.
25What is ?
Greatest common divisors and least common multiples
Medium
A.
B.
C.
D.
Correct Answer:
Explanation:
Since , the identity gives .
Incorrect! Try again.
26Use the Euclidean algorithm to determine .
Euclidean algorithm
Medium
A.
B.
C.
D.
Correct Answer:
Explanation:
Successive divisions give remainders . Therefore, the last nonzero remainder is .
Incorrect! Try again.
27Which pair satisfies the Bezout identity ?
Bezout's lemma
Medium
A.
B.
C.
D.
Correct Answer:
Explanation:
Substitution gives , so is a valid pair of Bezout coefficients.
Incorrect! Try again.
28What is the smallest positive integer that can be written as for some integers and ?
Bezout's lemma
Medium
A.
B.
C.
D.
Correct Answer:
Explanation:
By Bezout's lemma, the smallest positive integer of this form is .
Incorrect! Try again.
29Which set contains all incongruent solutions modulo of ?
Linear congruence
Medium
A.
B.
C.
D.
Correct Answer:
Explanation:
Dividing by gives . Since , , giving and modulo .
Incorrect! Try again.
30Which set contains all incongruent solutions modulo of ?
Linear congruence
Medium
A.
B.
C.
D.
Correct Answer:
Explanation:
Dividing by gives . Since , , producing modulo .
Incorrect! Try again.
31What is the multiplicative inverse of modulo ?
Inverse of a modulo m
Medium
A.
B.
C.
D.
Correct Answer:
Explanation:
The Euclidean algorithm gives . Hence is the inverse of .
Incorrect! Try again.
32Which integer has a multiplicative inverse modulo ?
Inverse of a modulo m
Medium
A.
B.
C.
D.
Correct Answer:
Explanation:
An integer has an inverse modulo exactly when it is relatively prime to . Only satisfies .
Incorrect! Try again.
33Find the least positive solution of the system , , and .
Chinese remainder theorem
Medium
A.
B.
C.
D.
Correct Answer:
Explanation:
The value gives remainders , , and when divided by , , and , respectively. The solution is unique modulo .
Incorrect! Try again.
34Find the least nonnegative solution of and .
Chinese remainder theorem
Medium
A.
B.
C.
D.
Correct Answer:
Explanation:
The number satisfies both congruences. Since , all solutions satisfy .
Incorrect! Try again.
35Using a Caesar cipher with encryption rule and the mapping , what is the ciphertext of MATH?
Encryption and decryption by Caesar cipher and affine transformation
Medium
A.QEXL
B.RFZN
C.RFYM
D.SGZN
Correct Answer: RFYM
Explanation:
Shifting each letter forward by gives , , , and .
Incorrect! Try again.
36A message was encrypted using a Caesar shift of . What plaintext corresponds to the ciphertext KHOOR?
Encryption and decryption by Caesar cipher and affine transformation
Medium
A.JGNNQ
B.KELLO
C.HELLO
D.IFMMP
Correct Answer: HELLO
Explanation:
Decryption shifts every letter backward by : , , , , and .
Incorrect! Try again.
37Using the affine cipher with , what is the encryption of CRYPTO?
Encryption and decryption by Caesar cipher and affine transformation
Medium
A.RQXEYZ
B.SPZFYA
C.SPYFZA
D.TQYGAB
Correct Answer: SPYFZA
Explanation:
Applying to the numerical values of CRYPTO gives , which correspond to SPYFZA.
Incorrect! Try again.
38An affine cipher uses with . Which plaintext letter encrypts to Z?
Encryption and decryption by Caesar cipher and affine transformation
Medium
A.R
B.T
C.Q
D.S
Correct Answer: S
Explanation:
The inverse of modulo is . For ciphertext value , , corresponding to S.
Incorrect! Try again.
39Using Fermat's little theorem, find the least nonnegative residue of modulo .
Fermat's little theorem
Medium
A.
B.
C.
D.
Correct Answer:
Explanation:
Since and , .
Incorrect! Try again.
40What is the remainder when is divided by ?
Fermat's little theorem
Medium
A.
B.
C.
D.
Correct Answer:
Explanation:
Fermat's little theorem gives . Since , .
Incorrect! Try again.
41What is the remainder when is divided by ?
Divisibility and modular arithmetic
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
Since , the powers of modulo have period . Also, , so .
Incorrect! Try again.
42Determine all integers for which divides .
Divisibility and modular arithmetic
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
Modulo , substitute to obtain . Thus , so , giving the stated set.
Incorrect! Try again.
43A prime satisfies . Which value must have?
Primes
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
For every prime , Fermat's theorem gives . Hence , so the prime must divide .
Incorrect! Try again.
44What is the greatest positive integer such that for every prime ?
Primes
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
Every prime is odd, so is divisible by . One of three consecutive integers is divisible by , and it cannot be . Thus . Taking shows no larger universal divisor is possible.
Incorrect! Try again.
45How many pairs of positive integers with satisfy and ?
Greatest common divisors and least common multiples
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
Write and , where . Then . Assigning each prime-power factor wholly to either or gives unordered pairs.
Incorrect! Try again.
46Evaluate .
Greatest common divisors and least common multiples
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
The identity applies. Since , the result is .
Incorrect! Try again.
47When the Euclidean algorithm is applied to and , what is the complete sequence of quotients, including the final exact division?
Euclidean algorithm
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
The divisions are , , , , and . Hence the quotient sequence is .
Incorrect! Try again.
48Suppose the Euclidean algorithm for positive integers has quotient sequence , where the last quotient corresponds to an exact division, and the last nonzero remainder is . What is ?
Euclidean algorithm
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
Reconstructing upward gives , , and . Thus .
Incorrect! Try again.
49Which family gives all integer solutions of ?
Bezout's lemma
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
A Bézout representation is . Since and , all solutions are and .
Incorrect! Try again.
50Among all integer pairs satisfying , which pair minimizes ?
Bezout's lemma
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
The Euclidean algorithm gives , so is a solution. All solutions are and , and uniquely minimizes .
Incorrect! Try again.
51What is the complete set of incongruent solutions modulo to ?
Linear congruence
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
Divide by to obtain . Since , , producing and modulo .
Incorrect! Try again.
52For which condition on the integer does have exactly six incongruent solutions modulo ?
Linear congruence
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
A congruence is solvable exactly when , and then it has solutions. Here , so precisely six solutions occur when .
Incorrect! Try again.
53What is the multiplicative inverse of modulo ?
Inverse of a modulo m
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
The extended Euclidean algorithm yields . Therefore .
Incorrect! Try again.
54Find the multiplicative inverse of modulo .
Inverse of a modulo m
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
Since , it follows that .
Incorrect! Try again.
55Find the complete solution to the non-coprime system and .
Chinese remainder theorem
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
The residues are compatible modulo . Among modulo , only is congruent to modulo , so .
Incorrect! Try again.
56What is the least nonnegative solution of the system , , and ?
Chinese remainder theorem
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
Combining the first two congruences gives . Modulo , this becomes , so . Therefore .
Incorrect! Try again.
57Using , a Caesar cipher encrypts by . What plaintext corresponds to the ciphertext XLEP?
Encryption and decryption by Caesar cipher and affine transformation
Hard
A.LATE
B.MATH
C.NAME
D.MATE
Correct Answer: MATE
Explanation:
Decryption subtracts modulo : , , , and . Thus the plaintext is MATE.
Incorrect! Try again.
58An affine cipher uses . If plaintext C encrypts to L and plaintext H encrypts to U, what does plaintext M encrypt to?
Encryption and decryption by Caesar cipher and affine transformation
Hard
A.D
B.F
C.P
D.J
Correct Answer: D
Explanation:
The known pairs give and . Thus , yielding and . For M, , which is D.
Incorrect! Try again.
59What is the remainder when is divided by ?
Fermat's little theorem
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
Fermat's theorem gives and . The unique residue modulo satisfying these conditions is .
Incorrect! Try again.
60What is the remainder modulo of ?
Fermat's little theorem
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
Every is nonzero modulo the prime , so Fermat's little theorem gives . The sum is therefore congruent to .
Incorrect! Try again.
Did this save you a night before the exam?
LPU Notes is free, and it stays free. Ads cover part of the server bill.
The rest comes out of a student's own pocket: the domain, the storage,
and keeping the site up through the weeks everyone needs it at once.
The payment button didn't load. An ad blocker or a filtered network is the usual reason.
to try again.
Nothing here is ever locked, and nothing unlocks. Chip in only if it was worth it.
What it pays for →