Unit 1: Number Theory-I - Subjective Questions

MTH381 — Number Theory And Cryptography • Practice Questions with Detailed Answers

20 questions

Define divisibility of integers. State and explain the Division Algorithm with a suitable example.

Explain the concept of modular arithmetic. What does $a \equiv b \pmod{m}$ mean? List and prove key properties of congruences.

Describe arithmetic modulo m. Define the set $\mathbb{Z}_m$ and the operations $+_m$ and $\cdot_m$ . Construct the addition and multiplication tables for $\mathbb{Z}_5$ .

Set $\mathbb{Z}_m$ : The set of non-negative integers less than $m$ :
$\mathbb{Z}_m = \{0, 1, 2, \ldots, m-1\}$

Addition modulo m ( $+_m$ ):
$a +_m b = (a + b) \bmod m$

Multiplication modulo m ( $\cdot_m$ ):
$a \cdot_m b = (a \cdot b) \bmod m$

These operations satisfy closure, associativity, commutativity, identity elements (0 for addition, 1 for multiplication), and additive inverses.

Addition Table for $\mathbb{Z}_5$ :

$+_5$	0	1	2	3	4
0	0	1	2	3	4
1	1	2	3	4	0
2	2	3	4	0	1
3	3	4	0	1	2
4	4	0	1	2	3

Multiplication Table for $\mathbb{Z}_5$ :

$\cdot_5$	1	2	3	4
0	0	0	0	0
1	1	2	3	4
2	2	4	1	3
3	3	1	4	2
4	4	3	2	1

Since 5 is prime, every non-zero element has a multiplicative inverse.

Explain the concept of base-b representation of integers. State and prove the theorem that guarantees a unique base- $b$ representation for every positive integer.

Describe the algorithm to convert a decimal integer to its binary expansion. Convert $(241)_{10}$ to binary showing all steps.

Algorithm (Repeated Division by 2):

Divide the decimal number by 2.
Record the remainder (0 or 1).
Replace the number with the quotient.
Repeat until the quotient is 0.
The binary expansion is the sequence of remainders read from bottom to top (last to first).

Converting $(241)_{10}$ :

Division	Quotient	Remainder
$241 \div 2$	120	1
$120 \div 2$	60	0
$60 \div 2$	30	0
$30 \div 2$	15	0
$15 \div 2$	7	1
$7 \div 2$	3	1
$3 \div 2$	1	1
$1 \div 2$	0	1

Reading remainders from bottom to top:
$(241)_{10} = (11110001)_2$

Verification: $128 + 64 + 32 + 16 + 1 = 241.$ ✓

Explain octal and hexadecimal number systems. Convert the decimal number $(2748)_{10}$ into both octal and hexadecimal expansions.

Octal System (Base 8): Uses digits $0$ – $7$ . Each octal digit represents a power of 8.

Hexadecimal System (Base 16): Uses digits $0$ – $9$ and letters $A$ – $F$ , where:
$A=10,\; B=11,\; C=12,\; D=13,\; E=14,\; F=15$

Converting $(2748)_{10}$ to Octal (repeated division by 8):

Division	Quotient	Remainder
$2748 \div 8$	343	4
$343 \div 8$	42	7
$42 \div 8$	5	2
$5 \div 8$	0	5

Reading bottom to top: $(2748)_{10} = (5274)_8$

Verification: $5\cdot512 + 2\cdot64 + 7\cdot8 + 4 = 2560 + 128 + 56 + 4 = 2748.$ ✓

Converting $(2748)_{10}$ to Hexadecimal (repeated division by 16):

Division	Quotient	Remainder
$2748 \div 16$	171	12 = C
$171 \div 16$	10	11 = B
$10 \div 16$	0	10 = A

Reading bottom to top: $(2748)_{10} = (ABC)_{16}$

Verification: $10\cdot256 + 11\cdot16 + 12 = 2560 + 176 + 12 = 2748.$ ✓

Explain the method of converting between binary, octal, and hexadecimal directly (without going through decimal). Illustrate with the binary number $(110101110)_2$ .

Describe the algorithm for the addition of two integers in binary representation. Add $(1101)_2$ and $(1011)_2$ using the algorithm, showing carries.

Addition Algorithm (Binary): Given two integers $a = (a_{n-1}\ldots a_1 a_0)_2$ and $b = (b_{n-1}\ldots b_1 b_0)_2$ , we add bit by bit from the least significant bit, propagating carries.

Steps:

Initialize carry $c = 0$ .
For each bit position from 0 to :
- Compute sum $= a_j + b_j + c$
- The result bit $s_j = \text{sum} \bmod 2$
- New carry $c = \lfloor \text{sum}/2 \rfloor$
The final carry becomes the leading bit $s_n$ .

Bit-Rules: $0+0=0$ , $0+1=1$ , $1+1=10$ (write 0, carry 1), $1+1+1=11$ (write 1, carry 1).

Adding $(1101)_2 + (1011)_2$ :

carries: 1 1 1 1
1 1 0 1

1 0 1 1
```
 1 1 0 0 0
```

Step-by-step:

Bit 0: $1+1 = 10 \Rightarrow$ write 0, carry 1
Bit 1: $0+1+1 = 10 \Rightarrow$ write 0, carry 1
Bit 2: $1+0+1 = 10 \Rightarrow$ write 0, carry 1
Bit 3: $1+1+1 = 11 \Rightarrow$ write 1, carry 1
Final carry: write 1

Result: $(11000)_2 = 24$ .

Verification: $13 + 11 = 24$ ✓ (Complexity: $O(n)$ bit operations).

Describe the algorithm for multiplication of two integers in binary. Multiply $(101)_2$ by $(110)_2$ using the shift-and-add method. Analyze its complexity.

Multiplication Algorithm (Binary): To multiply $a = (a_{n-1}\ldots a_0)_2$ by $b = (b_{n-1}\ldots b_0)_2$ :

For each bit of : form a partial product.
- If $b_j = 1$ , the partial product is $a$ shifted left by $j$ positions ( $a \cdot 2^j$ ).
- If $b_j = 0$ , the partial product is 0.
Add all partial products using the binary addition algorithm.

$ab = \sum_{j=0}^{n-1} (a b_j) 2^j$

Multiplying $(101)_2 \times (110)_2$ :

$a = 101,\; b = 110$ (bits $b_0=0, b_1=1, b_2=1$ )

$b_0 = 0$ : partial product $= 000$
$b_1 = 1$ : partial product $= 101$ shifted 1 $= 1010$
$b_2 = 1$ : partial product $= 101$ shifted 2 $= 10100$
```
 1 0 1
```
x 1 1 0

0 0 0 0 0 (b0 = 0)
1 0 1 0 (b1 = 1, shift 1)
1 0 1 0 0 (b2 = 1, shift 2)

1 1 1 1 0

Result: $(11110)_2 = 30$ .

Verification: $5 \times 6 = 30$ ✓

Complexity Analysis: There are $n$ partial products, each of length up to $2n$ bits. Computing shifts is $O(n)$ and adding $n$ numbers of length $O(n)$ takes $O(n^2)$ bit operations. Hence total complexity is $O(n^2)$ .

Distinguish between the notations $a \bmod m$ (the modulo operator) and $a \equiv b \pmod{m}$ (congruence relation). Give examples of each.

$a \bmod m$ (Modulo Operator):

This is a binary operation (function) that returns a single value — the remainder when $a$ is divided by $m$ .
The result is always in the range $\{0, 1, \ldots, m-1\}$ .
Example: $17 \bmod 5 = 2$ .

$a \equiv b \pmod{m}$ (Congruence Relation):

This is a relation (a statement that is either true or false) between two integers $a$ and $b$ .
It asserts that $m \mid (a - b)$ , i.e., $a$ and $b$ have the same remainder mod $m$ .
Example: $17 \equiv 2 \pmod 5$ is true; $17 \equiv 3 \pmod 5$ is false.

Comparison Table:

Aspect	$a \bmod m$	$a \equiv b \pmod{m}$
Type	Function/operator	Relation (true/false)
Output	A number in $[0, m-1]$	A boolean statement
Reads as	" $a$ modulo $m$ "	" $a$ is congruent to $b$ mod $m$ "
Example	$23 \bmod 7 = 2$	$23 \equiv 9 \pmod 7$

Relationship: $a \equiv b \pmod m$ is true if and only if $a \bmod m = b \bmod m$ .

State and prove the following properties of divisibility: (a) If $a \mid b$ and $a \mid c$ , then $a \mid (b + c)$ . (b) If $a \mid b$ , then $a \mid bc$ for any integer $c$ . (c) If $a \mid b$ and $b \mid c$ , then $a \mid c$ .

Explain how modular arithmetic is used to compute the day of the week and other cyclic phenomena. Using modulo 7, determine the day of the week 100 days after a Monday.

Convert the hexadecimal number $(3AF)_{16}$ to (a) binary, (b) octal, and (c) decimal. Show the working for each conversion.

Given $(3AF)_{16}$ where $A = 10$ , $F = 15$ .

(a) Hexadecimal to Binary: Convert each hex digit to 4 bits.

Hex digit	4-bit binary
3	0011
A	1010
F	1111

Concatenating: $(001110101111)_2$ . Dropping leading zeros:
$(3AF)_{16} = (1110101111)_2$

(b) Hexadecimal to Octal (via binary): Take the binary $001110101111$ and regroup into 3-bit sets from the right:
$001\;\;110\;\;101\;\;111$
$001=1,\;110=6,\;101=5,\;111=7$
$\Rightarrow (1657)_8$

(c) Hexadecimal to Decimal: Use positional values (powers of 16):
$(3AF)_{16} = 3 \times 16^2 + 10 \times 16^1 + 15 \times 16^0$
$= 3 \times 256 + 10 \times 16 + 15$
$= 768 + 160 + 15 = 943$

Verification: $(1657)_8 = 1\cdot512 + 6\cdot64 + 5\cdot8 + 7 = 512+384+40+7 = 943$ ✓

Explain the number of bit operations required for the standard integer addition algorithm. Derive the time complexity for adding two $n$ -bit numbers.

Define the greatest integer function (floor) and least integer function (ceiling). Explain their role in the division algorithm and evaluate $\lfloor -7/3 \rfloor$ , $\lceil -7/3 \rceil$ , $\lfloor 7/3 \rfloor$ , and $\lceil 7/3 \rceil$ .

Compare the binary, octal, hexadecimal, and decimal number systems in a tabular form, discussing base, digits used, and typical applications. Why are octal and hexadecimal preferred in computing?

Comparison Table:

System	Base	Digits Used	Prefix (common)	Application
Binary	2	0, 1	`0b`	Internal machine representation, digital logic
Octal	8	0–7	`0o`	Unix file permissions, compact binary grouping
Decimal	10	0–9	(none)	Everyday human arithmetic
Hexadecimal	16	0–9, A–F	`0x`	Memory addresses, color codes, machine code

Why Octal and Hexadecimal are Preferred in Computing:

Compact representation of binary: Computers work in binary, but long binary strings are error-prone to read/write. Since $8 = 2^3$ and $16 = 2^4$ , conversion between binary and octal/hex is trivial — each octal digit maps to exactly 3 bits and each hex digit to exactly 4 bits.
Example: The 8-bit value $(11010110)_2$ is $(326)_8$ or $(D6)_{16}$ — far shorter and easier to handle.
No arithmetic conversion needed: Grouping bits directly gives the octal/hex digits, avoiding tedious division.
Hex dominance today: Because modern computers use byte (8-bit) and word sizes that are multiples of 4 bits, hexadecimal aligns perfectly (2 hex digits = 1 byte), making it the standard for memory dumps, addresses, and color codes (e.g., #FF8800).

Thus octal/hex act as a convenient human-readable shorthand for binary.

Explain fast modular exponentiation using the method of successive squaring. Compute $3^{13} \bmod 7$ using this technique.

Convert the octal number $(725)_8$ to binary, hexadecimal, and decimal. Clearly explain each conversion step.

Given $(725)_8$ .

(a) Octal to Binary: Convert each octal digit to 3 bits.

Octal digit	3-bit binary
7	111
2	010
5	101

Concatenating: $(725)_8 = (111010101)_2$

(b) Octal/Binary to Hexadecimal: Take binary $111010101$ and regroup into 4-bit sets from the right (pad left with zeros):
$0001\;\;1101\;\;0101$
$0001 = 1,\quad 1101 = D,\quad 0101 = 5$
$\Rightarrow (1D5)_{16}$

(c) Octal to Decimal: Use positional powers of 8:
$(725)_8 = 7 \times 8^2 + 2 \times 8^1 + 5 \times 8^0$
$= 7 \times 64 + 2 \times 8 + 5$
$= 448 + 16 + 5 = 469$

Verification via hex: $(1D5)_{16} = 1\cdot256 + 13\cdot16 + 5 = 256 + 208 + 5 = 469$ ✓

State the Well-Ordering Principle and use it to prove the existence part of the Division Algorithm.

Explain how integers are added and multiplied in arithmetic modulo m by giving the general rules, and perform the following computations in $\mathbb{Z}_{11}$ : (a) $7 +_{11} 9$ , (b) $8 \cdot_{11} 6$ , (c) the additive inverse of $4$ , (d) $(5 \cdot_{11} 5) +_{11} 8$ .

Question 1

Define divisibility of integers. State and explain the Division Algorithm with a suitable example.

Tap card to reveal answer

Answer 1

Divisibility: An integer $a$ divides an integer $b$ (written $a \mid b$ ) if there exists an integer $c$ such that $b = ac$ . Here $a$ is called a divisor or factor of $b$ , and $b$ is a multiple of $a$ .

Division Algorithm: For any integer $a$ and positive integer $d$ , there exist unique integers $q$ (the quotient) and $r$ (the remainder) such that:
$a = dq + r, \quad 0 \le r < d$

$q = \lfloor a/d \rfloor$ (floor of $a/d$ )
$r = a - dq = a \bmod d$

Example: Let $a = 17$ and $d = 5$ .
$17 = 5 \times 3 + 2$
Here $q = 3$ and $r = 2$ , where $0 \le 2 < 5$ .

Example with negative dividend: Let $a = -17$ , $d = 5$ .
$-17 = 5 \times (-4) + 3$
Here $q = -4$ and $r = 3$ (remainder is always non-negative).

Tap card to flip back

Question 2

Explain the concept of modular arithmetic. What does $a \equiv b \pmod{m}$ mean? List and prove key properties of congruences.

Tap card to reveal answer

Answer 2

Congruence Modulo m: Two integers $a$ and $b$ are said to be congruent modulo $m$ (where $m$ is a positive integer) if $m$ divides $(a - b)$ . It is written as:
$a \equiv b \pmod{m} \iff m \mid (a - b)$

Equivalently, $a$ and $b$ leave the same remainder when divided by $m$ .

Key Properties:

Reflexive: $a \equiv a \pmod{m}$
Symmetric: If $a \equiv b \pmod{m}$ , then $b \equiv a \pmod{m}$
Transitive: If $a \equiv b$ and $b \equiv c \pmod{m}$ , then $a \equiv c \pmod{m}$

Addition/Multiplication Property: If $a \equiv b \pmod{m}$ and $c \equiv d \pmod{m}$ , then:
$a + c \equiv b + d \pmod{m}$
$ac \equiv bd \pmod{m}$

Proof of Multiplication Property: Since $a \equiv b$ , we have $a = b + km$ ; since $c \equiv d$ , we have $c = d + lm$ for integers $k, l$ . Then:
$ac = (b+km)(d+lm) = bd + m(bl + dk + klm)$
Thus $ac - bd = m(bl + dk + klm)$ , which is divisible by $m$ , so $ac \equiv bd \pmod{m}$ .

Example: $17 \equiv 5 \pmod{6}$ because $6 \mid (17 - 5) = 12$ .

Tap card to flip back

Question 3

Describe arithmetic modulo m. Define the set $\mathbb{Z}_m$ and the operations $+_m$ and $\cdot_m$ . Construct the addition and multiplication tables for $\mathbb{Z}_5$ .

Tap card to reveal answer

Answer 3

Set $\mathbb{Z}_m$ : The set of non-negative integers less than $m$ :
$\mathbb{Z}_m = \{0, 1, 2, \ldots, m-1\}$

Addition modulo m ( $+_m$ ):
$a +_m b = (a + b) \bmod m$

Multiplication modulo m ( $\cdot_m$ ):
$a \cdot_m b = (a \cdot b) \bmod m$

These operations satisfy closure, associativity, commutativity, identity elements (0 for addition, 1 for multiplication), and additive inverses.

Addition Table for $\mathbb{Z}_5$ :

$+_5$	0	1	2	3	4
0	0	1	2	3	4
1	1	2	3	4	0
2	2	3	4	0	1
3	3	4	0	1	2
4	4	0	1	2	3

Multiplication Table for $\mathbb{Z}_5$ :

$\cdot_5$	1	2	3	4
0	0	0	0	0
1	1	2	3	4
2	2	4	1	3
3	3	1	4	2
4	4	3	2	1

Since 5 is prime, every non-zero element has a multiplicative inverse.

Tap card to flip back

Question 4

Explain the concept of base-b representation of integers. State and prove the theorem that guarantees a unique base- $b$ representation for every positive integer.

Tap card to reveal answer

Answer 4

Base-b Representation Theorem: Let $b > 1$ be an integer. Then every positive integer $n$ can be expressed uniquely in the form:
$n = a_k b^k + a_{k-1} b^{k-1} + \cdots + a_1 b + a_0$
where $k \ge 0$ , each digit $a_i$ satisfies $0 \le a_i < b$ , and the leading digit $a_k \neq 0$ .

This is written as $(a_k a_{k-1} \ldots a_1 a_0)_b$ .

Proof (Existence by construction): Apply the division algorithm repeatedly:
$n = b q_0 + a_0, \quad 0 \le a_0 < b$
$q_0 = b q_1 + a_1, \quad 0 \le a_1 < b$
$\vdots$
Continue until the quotient becomes 0. Since $n > q_0 > q_1 > \cdots \ge 0$ is a strictly decreasing sequence of non-negative integers, the process terminates. The remainders $a_0, a_1, \ldots, a_k$ form the base- $b$ digits.

Uniqueness: Suppose $n$ has two representations. The first digit $a_0 = n \bmod b$ is uniquely determined. Then $q_0 = (n - a_0)/b$ is unique, and by induction all subsequent digits are uniquely determined.

Example (base 2): $13 = 1\cdot 8 + 1\cdot 4 + 0\cdot 2 + 1 = (1101)_2$ .

Tap card to flip back

Question 5

Describe the algorithm to convert a decimal integer to its binary expansion. Convert $(241)_{10}$ to binary showing all steps.

Tap card to reveal answer

Answer 5

Algorithm (Repeated Division by 2):

Divide the decimal number by 2.
Record the remainder (0 or 1).
Replace the number with the quotient.
Repeat until the quotient is 0.
The binary expansion is the sequence of remainders read from bottom to top (last to first).

Converting $(241)_{10}$ :

Division	Quotient	Remainder
$241 \div 2$	120	1
$120 \div 2$	60	0
$60 \div 2$	30	0
$30 \div 2$	15	0
$15 \div 2$	7	1
$7 \div 2$	3	1
$3 \div 2$	1	1
$1 \div 2$	0	1

Reading remainders from bottom to top:
$(241)_{10} = (11110001)_2$

Verification: $128 + 64 + 32 + 16 + 1 = 241.$ ✓

Tap card to flip back

Question 6

Explain octal and hexadecimal number systems. Convert the decimal number $(2748)_{10}$ into both octal and hexadecimal expansions.

Tap card to reveal answer

Answer 6

Octal System (Base 8): Uses digits $0$ – $7$ . Each octal digit represents a power of 8.

Hexadecimal System (Base 16): Uses digits $0$ – $9$ and letters $A$ – $F$ , where:
$A=10,\; B=11,\; C=12,\; D=13,\; E=14,\; F=15$

Converting $(2748)_{10}$ to Octal (repeated division by 8):

Division	Quotient	Remainder
$2748 \div 8$	343	4
$343 \div 8$	42	7
$42 \div 8$	5	2
$5 \div 8$	0	5

Reading bottom to top: $(2748)_{10} = (5274)_8$

Verification: $5\cdot512 + 2\cdot64 + 7\cdot8 + 4 = 2560 + 128 + 56 + 4 = 2748.$ ✓

Converting $(2748)_{10}$ to Hexadecimal (repeated division by 16):

Division	Quotient	Remainder
$2748 \div 16$	171	12 = C
$171 \div 16$	10	11 = B
$10 \div 16$	0	10 = A

Reading bottom to top: $(2748)_{10} = (ABC)_{16}$

Verification: $10\cdot256 + 11\cdot16 + 12 = 2560 + 176 + 12 = 2748.$ ✓

Tap card to flip back

Question 7

Explain the method of converting between binary, octal, and hexadecimal directly (without going through decimal). Illustrate with the binary number $(110101110)_2$ .

Tap card to reveal answer

Answer 7

Key Idea: Since $8 = 2^3$ and $16 = 2^4$ :

Binary ↔ Octal: Group binary digits in sets of 3 (from right).
Binary ↔ Hexadecimal: Group binary digits in sets of 4 (from right).

Binary to Octal — $(110101110)_2$ :

Group into 3 bits from the right:
$110\;\;101\;\;110$
$110 = 6, \quad 101 = 5, \quad 110 = 6$
$\Rightarrow (656)_8$

Binary to Hexadecimal — $(110101110)_2$ :

Group into 4 bits from the right (pad left with zeros):
$0001\;\;1010\;\;1110$
$0001 = 1, \quad 1010 = A, \quad 1110 = E$
$\Rightarrow (1AE)_{16}$

Octal to Hexadecimal (via binary): Convert each octal digit to 3 bits, then regroup into 4-bit sets.

Verification: $(110101110)_2 = 256+128+0+32+0+8+4+2+0 = 430$ . Also $(656)_8 = 6\cdot64+5\cdot8+6 = 430$ ✓ and $(1AE)_{16} = 256+160+14 = 430$ ✓.

Tap card to flip back

Question 8

Describe the algorithm for the addition of two integers in binary representation. Add $(1101)_2$ and $(1011)_2$ using the algorithm, showing carries.

Tap card to reveal answer

Answer 8

Addition Algorithm (Binary): Given two integers $a = (a_{n-1}\ldots a_1 a_0)_2$ and $b = (b_{n-1}\ldots b_1 b_0)_2$ , we add bit by bit from the least significant bit, propagating carries.

Steps:

Initialize carry $c = 0$ .
For each bit position from 0 to :
- Compute sum $= a_j + b_j + c$
- The result bit $s_j = \text{sum} \bmod 2$
- New carry $c = \lfloor \text{sum}/2 \rfloor$
The final carry becomes the leading bit $s_n$ .

Bit-Rules: $0+0=0$ , $0+1=1$ , $1+1=10$ (write 0, carry 1), $1+1+1=11$ (write 1, carry 1).

Adding $(1101)_2 + (1011)_2$ :

carries: 1 1 1 1
1 1 0 1

1 0 1 1
```
 1 1 0 0 0
```

Step-by-step:

Bit 0: $1+1 = 10 \Rightarrow$ write 0, carry 1
Bit 1: $0+1+1 = 10 \Rightarrow$ write 0, carry 1
Bit 2: $1+0+1 = 10 \Rightarrow$ write 0, carry 1
Bit 3: $1+1+1 = 11 \Rightarrow$ write 1, carry 1
Final carry: write 1

Result: $(11000)_2 = 24$ .

Verification: $13 + 11 = 24$ ✓ (Complexity: $O(n)$ bit operations).

Tap card to flip back

Question 9

Describe the algorithm for multiplication of two integers in binary. Multiply $(101)_2$ by $(110)_2$ using the shift-and-add method. Analyze its complexity.

Tap card to reveal answer

Answer 9

Multiplication Algorithm (Binary): To multiply $a = (a_{n-1}\ldots a_0)_2$ by $b = (b_{n-1}\ldots b_0)_2$ :

For each bit of : form a partial product.
- If $b_j = 1$ , the partial product is $a$ shifted left by $j$ positions ( $a \cdot 2^j$ ).
- If $b_j = 0$ , the partial product is 0.
Add all partial products using the binary addition algorithm.

$ab = \sum_{j=0}^{n-1} (a b_j) 2^j$

Multiplying $(101)_2 \times (110)_2$ :

$a = 101,\; b = 110$ (bits $b_0=0, b_1=1, b_2=1$ )

$b_0 = 0$ : partial product $= 000$
$b_1 = 1$ : partial product $= 101$ shifted 1 $= 1010$
$b_2 = 1$ : partial product $= 101$ shifted 2 $= 10100$
```
 1 0 1
```
x 1 1 0

0 0 0 0 0 (b0 = 0)
1 0 1 0 (b1 = 1, shift 1)
1 0 1 0 0 (b2 = 1, shift 2)

1 1 1 1 0

Result: $(11110)_2 = 30$ .

Verification: $5 \times 6 = 30$ ✓

Tap card to flip back

Question 10

Distinguish between the notations $a \bmod m$ (the modulo operator) and $a \equiv b \pmod{m}$ (congruence relation). Give examples of each.

Tap card to reveal answer

Answer 10

$a \bmod m$ (Modulo Operator):

This is a binary operation (function) that returns a single value — the remainder when $a$ is divided by $m$ .
The result is always in the range $\{0, 1, \ldots, m-1\}$ .
Example: $17 \bmod 5 = 2$ .

$a \equiv b \pmod{m}$ (Congruence Relation):

This is a relation (a statement that is either true or false) between two integers $a$ and $b$ .
It asserts that $m \mid (a - b)$ , i.e., $a$ and $b$ have the same remainder mod $m$ .
Example: $17 \equiv 2 \pmod 5$ is true; $17 \equiv 3 \pmod 5$ is false.

Comparison Table:

Aspect	$a \bmod m$	$a \equiv b \pmod{m}$
Type	Function/operator	Relation (true/false)
Output	A number in $[0, m-1]$	A boolean statement
Reads as	" $a$ modulo $m$ "	" $a$ is congruent to $b$ mod $m$ "
Example	$23 \bmod 7 = 2$	$23 \equiv 9 \pmod 7$

Relationship: $a \equiv b \pmod m$ is true if and only if $a \bmod m = b \bmod m$ .

Tap card to flip back

Question 11

Tap card to reveal answer

Answer 11

Let $a, b, c$ be integers with $a \neq 0$ .

(a) If $a \mid b$ and $a \mid c$ , then $a \mid (b+c)$ :

Since $a \mid b$ , there exists integer $s$ with $b = as$ . Since $a \mid c$ , there exists integer $t$ with $c = at$ . Then:
$b + c = as + at = a(s + t)$
Since $(s+t)$ is an integer, $a \mid (b+c)$ . $\blacksquare$

(b) If $a \mid b$ , then $a \mid bc$ for any integer $c$ :

Since $a \mid b$ , there exists integer $s$ with $b = as$ . Then:
$bc = (as)c = a(sc)$
Since $(sc)$ is an integer, $a \mid bc$ . $\blacksquare$

(c) If $a \mid b$ and $b \mid c$ , then $a \mid c$ (Transitivity):

Since $a \mid b$ , there exists integer $s$ with $b = as$ . Since $b \mid c$ , there exists integer $t$ with $c = bt$ . Substituting:
$c = bt = (as)t = a(st)$
Since $(st)$ is an integer, $a \mid c$ . $\blacksquare$

Corollary (Linear Combination): From (a) and (b), if $a \mid b$ and $a \mid c$ , then $a \mid (mb + nc)$ for all integers $m, n$ .

Tap card to flip back

Question 12

Explain how modular arithmetic is used to compute the day of the week and other cyclic phenomena. Using modulo 7, determine the day of the week 100 days after a Monday.

Tap card to reveal answer

Answer 12

Cyclic Phenomena and Modular Arithmetic: Many real-world quantities repeat in cycles — days of the week (period 7), hours on a clock (period 12 or 24), months (period 12). Modular arithmetic naturally models these because after reaching the modulus, values wrap back to 0.

If we label days as: Monday $= 0$ , Tuesday $= 1$ , ..., Sunday $= 6$ , then the day $n$ days later is:
$\text{day} = (\text{start} + n) \bmod 7$

Problem: 100 days after Monday

Start = Monday = $0$
Compute $(0 + 100) \bmod 7$
$100 = 7 \times 14 + 2$ , so $100 \bmod 7 = 2$

Result = $2$ , which corresponds to Wednesday.

Other Examples:

12-hour clock: Time $t$ hours after time $h$ is $(h + t) \bmod 12$ .
ISBN/checksum digits: Use mod 10 or mod 11.
Cryptography: Caesar cipher shifts letters using mod 26.

Thus modular arithmetic elegantly captures periodic/wrapping behavior.

Tap card to flip back

Question 13

Convert the hexadecimal number $(3AF)_{16}$ to (a) binary, (b) octal, and (c) decimal. Show the working for each conversion.

Tap card to reveal answer

Answer 13

Given $(3AF)_{16}$ where $A = 10$ , $F = 15$ .

(a) Hexadecimal to Binary: Convert each hex digit to 4 bits.

Hex digit	4-bit binary
3	0011
A	1010
F	1111

Concatenating: $(001110101111)_2$ . Dropping leading zeros:
$(3AF)_{16} = (1110101111)_2$

(b) Hexadecimal to Octal (via binary): Take the binary $001110101111$ and regroup into 3-bit sets from the right:
$001\;\;110\;\;101\;\;111$
$001=1,\;110=6,\;101=5,\;111=7$
$\Rightarrow (1657)_8$

(c) Hexadecimal to Decimal: Use positional values (powers of 16):
$(3AF)_{16} = 3 \times 16^2 + 10 \times 16^1 + 15 \times 16^0$
$= 3 \times 256 + 10 \times 16 + 15$
$= 768 + 160 + 15 = 943$

Verification: $(1657)_8 = 1\cdot512 + 6\cdot64 + 5\cdot8 + 7 = 512+384+40+7 = 943$ ✓

Tap card to flip back

Question 14

Explain the number of bit operations required for the standard integer addition algorithm. Derive the time complexity for adding two $n$ -bit numbers.

Tap card to reveal answer

Answer 14

Setup: Let $a$ and $b$ be two integers each represented with $n$ bits (if unequal, pad the shorter with leading zeros so both have $n$ bits).

Addition Procedure: We add bit by bit from the least significant to the most significant bit, maintaining a carry.

At each bit position $j$ :
$s_j = (a_j + b_j + c_j) \bmod 2, \qquad c_{j+1} = \left\lfloor \frac{a_j + b_j + c_j}{2} \right\rfloor$

Counting Operations:

At bit position 0: adding $a_0 + b_0$ requires 1 bit addition (no incoming carry).
At each subsequent position $j$ (from 1 to $n-1$ ): we add three bits ( $a_j, b_j, c_j$ ), which requires a constant number ( $\le 2$ ) of bit operations.

Thus the total number of bit operations is:
$1 + \underbrace{2 + 2 + \cdots + 2}_{n-1 \text{ terms}} = 1 + 2(n-1) = 2n - 1$

Time Complexity: Since each bit position needs $O(1)$ bit operations and there are $n$ positions:
$T(n) = O(n)$

Conclusion: The addition of two $n$ -bit integers requires a number of bit operations that is linear in $n$ , i.e., $\Theta(n)$ . This is optimal since every bit of the input must be examined at least once.

Tap card to flip back

Question 16

Compare the binary, octal, hexadecimal, and decimal number systems in a tabular form, discussing base, digits used, and typical applications. Why are octal and hexadecimal preferred in computing?

Tap card to reveal answer

Answer 16

Comparison Table:

System	Base	Digits Used	Prefix (common)	Application
Binary	2	0, 1	`0b`	Internal machine representation, digital logic
Octal	8	0–7	`0o`	Unix file permissions, compact binary grouping
Decimal	10	0–9	(none)	Everyday human arithmetic
Hexadecimal	16	0–9, A–F	`0x`	Memory addresses, color codes, machine code

Why Octal and Hexadecimal are Preferred in Computing:

Compact representation of binary: Computers work in binary, but long binary strings are error-prone to read/write. Since $8 = 2^3$ and $16 = 2^4$ , conversion between binary and octal/hex is trivial — each octal digit maps to exactly 3 bits and each hex digit to exactly 4 bits.
Example: The 8-bit value $(11010110)_2$ is $(326)_8$ or $(D6)_{16}$ — far shorter and easier to handle.
No arithmetic conversion needed: Grouping bits directly gives the octal/hex digits, avoiding tedious division.
Hex dominance today: Because modern computers use byte (8-bit) and word sizes that are multiples of 4 bits, hexadecimal aligns perfectly (2 hex digits = 1 byte), making it the standard for memory dumps, addresses, and color codes (e.g., #FF8800).

Thus octal/hex act as a convenient human-readable shorthand for binary.

Tap card to flip back

Question 17

Explain fast modular exponentiation using the method of successive squaring. Compute $3^{13} \bmod 7$ using this technique.

Tap card to reveal answer

Answer 17

Fast Modular Exponentiation (Binary/Successive Squaring): To compute $a^n \bmod m$ efficiently, we use the binary expansion of the exponent $n$ and repeated squaring, reducing modulo $m$ at each step. This avoids computing the huge number $a^n$ directly.

If $n = (b_{k}b_{k-1}\ldots b_0)_2$ , then:
$a^n = \prod_{b_i = 1} a^{2^i} \pmod m$

Algorithm:

Write $n$ in binary.
Compute successive squares $a^{2^0}, a^{2^1}, a^{2^2}, \ldots \pmod m$ .
Multiply together those squares corresponding to a 1-bit in $n$ , reducing mod $m$ .

Compute $3^{13} \bmod 7$ :

Binary of exponent: $13 = (1101)_2 = 8 + 4 + 1$ , so $3^{13} = 3^{8} \cdot 3^{4} \cdot 3^{1}$ .

Successive squaring mod 7:
$3^1 \equiv 3 \pmod 7$
$3^2 = 9 \equiv 2 \pmod 7$
$3^4 = (3^2)^2 = 2^2 = 4 \pmod 7$
$3^8 = (3^4)^2 = 4^2 = 16 \equiv 2 \pmod 7$

Combine (bits 8, 4, 1 are set):
$3^{13} \equiv 3^8 \cdot 3^4 \cdot 3^1 \equiv 2 \cdot 4 \cdot 3 = 24 \equiv 3 \pmod 7$

Result: $3^{13} \bmod 7 = 3$ .

Efficiency: Only $O(\log n)$ multiplications are needed instead of $n-1$ , making this crucial for cryptographic applications like RSA.

Tap card to flip back

Question 18

Convert the octal number $(725)_8$ to binary, hexadecimal, and decimal. Clearly explain each conversion step.

Tap card to reveal answer

Answer 18

Given $(725)_8$ .

(a) Octal to Binary: Convert each octal digit to 3 bits.

Octal digit	3-bit binary
7	111
2	010
5	101

Concatenating: $(725)_8 = (111010101)_2$

(c) Octal to Decimal: Use positional powers of 8:
$(725)_8 = 7 \times 8^2 + 2 \times 8^1 + 5 \times 8^0$
$= 7 \times 64 + 2 \times 8 + 5$
$= 448 + 16 + 5 = 469$

Verification via hex: $(1D5)_{16} = 1\cdot256 + 13\cdot16 + 5 = 256 + 208 + 5 = 469$ ✓

Tap card to flip back

Question 19

State the Well-Ordering Principle and use it to prove the existence part of the Division Algorithm.

Tap card to reveal answer

Answer 19

Well-Ordering Principle (WOP): Every non-empty set of non-negative integers has a least element.

Division Algorithm (Existence): For any integer $a$ and positive integer $d$ , there exist integers $q$ and $r$ such that $a = dq + r$ with $0 \le r < d$ .

Proof of Existence using WOP:

Consider the set of all non-negative values of the form $a - dq$ :
$S = \{ a - dq : q \in \mathbb{Z}, \; a - dq \ge 0 \}$

Step 1 — $S$ is non-empty: We can choose $q$ small enough (very negative) so that $a - dq \ge 0$ . For example, take $q = -|a|$ ; then $a - d(-|a|) = a + d|a| \ge 0$ since $d \ge 1$ . So $S \neq \emptyset$ .

Step 2 — Apply WOP: Since $S$ is a non-empty set of non-negative integers, it has a least element. Call it $r = a - dq$ for some integer $q$ . By construction $r \ge 0$ .

Step 3 — Show $r < d$ : Suppose, for contradiction, that $r \ge d$ . Then:
$a - d(q+1) = (a - dq) - d = r - d \ge 0$
This means $r - d \in S$ , but $r - d < r$ , contradicting that $r$ is the least element of $S$ .

Therefore $0 \le r < d$ , completing the existence proof. $\blacksquare$

Note: Uniqueness is proved separately by assuming two representations and showing they must be equal.

Tap card to flip back

1 / 20

Unit2

Unit 1: Number Theory-I - Subjective Questions

1 0 1 1

x 1 1 0

0 0 0 0 0 (b0 = 0) 1 0 1 0 (b1 = 1, shift 1) 1 0 1 0 0 (b2 = 1, shift 2)

1 0 1 1

x 1 1 0

0 0 0 0 0 (b0 = 0) 1 0 1 0 (b1 = 1, shift 1) 1 0 1 0 0 (b2 = 1, shift 2)

Did this save you a night before the exam?

0 0 0 0 0 (b0 = 0)
1 0 1 0 (b1 = 1, shift 1)
1 0 1 0 0 (b2 = 1, shift 2)

0 0 0 0 0 (b0 = 0)
1 0 1 0 (b1 = 1, shift 1)
1 0 1 0 0 (b2 = 1, shift 2)