Unit 2: Basic math operations (addition, subtraction, multiplication, division and exponentiation) - Subjective Questions

Fast Modulo Multiplication is a technique used to compute without causing integer overflow, even when and are very large numbers.

Why it is needed:

• When and are close to the maximum value of a data type (e.g., ), their product can overflow a 64-bit integer.
• Direct multiplication before taking modulo produces incorrect results.

Approach (Russian Peasant / Binary Multiplication):
We express multiplication as repeated addition using the binary representation of :

At each step we take modulo to keep values small.

Algorithm:

• Initialize result = 0, a = a % m.
• While b > 0:
  • If b is odd: result = (result + a) % m
  • a = (2 * a) % m
  • b = b / 2

Example: Compute .

• , so effectively .
• Using the algorithm the result is , which matches .

This runs in time and guarantees no overflow.

Exponentiation by Squaring is an efficient method to compute in time instead of the naive approach.

Core Idea:
We use the recursive relations:

Iterative Algorithm:

• Initialize result = 1, base = a.
• While n > 0:
  • If n is odd: result = result * base
  • base = base * base
  • n = n / 2

Example: Compute .

• .

Time Complexity Derivation:

• Each step halves , so the number of iterations is .
• Each iteration performs a constant number of multiplications.
• Therefore the total complexity is .

This is dramatically faster than repeated multiplication for large exponents.

A non-square number is a positive integer that is not a perfect square (i.e., not ).

Goal: Find the -th non-square number directly.

Derivation:

• Among the first natural numbers, the count of perfect squares is .
• So the number of non-squares up to is .
• We want the value such that it is the -th non-square.

Formula:

A commonly used simpler form is:

Explanation: The term counts how many perfect squares lie below the target, so we shift by that many positions.

Example: For :

• Result .
• Checking the sequence of non-squares: — the 5th is indeed . ✓

This gives an solution.

Modular Exponentiation is the operation of computing efficiently, which is fundamental in cryptography (e.g., RSA) and number theory.

Why efficient computation is needed:

• grows extremely fast and cannot be stored directly.
• We apply modulo at each step to keep intermediate values small.

Key property:

Algorithm (Binary/Fast Modular Exponentiation):

• Initialize result = 1, a = a % m.
• While b > 0:
  • If b is odd: result = (result * a) % m
  • b = b >> 1 (integer divide by 2)
  • a = (a * a) % m
• Return result.

Example: Compute .

• , so .
• The algorithm yields using multiplications.

Time Complexity: — logarithmic in the exponent.

Note: For very large , combine this with fast modulo multiplication to prevent overflow during .

The Modular Multiplicative Inverse of an integer under modulo is an integer such that:

It is often denoted as .

Condition for Existence:

• The inverse exists if and only if , i.e., and are coprime.
• If , no inverse exists.

Why it matters:

• Division is not directly defined in modular arithmetic. To compute , we multiply by the inverse: .

Methods to compute:

• Extended Euclidean Algorithm: Solves ; the value is the inverse. Works for any coprime .
• Fermat's Little Theorem: If is prime and , then .

Example: Inverse of modulo .

• We need .
• , so the inverse is .

Fermat's Little Theorem states that if is a prime and is an integer not divisible by , then:

Derivation of the Inverse:

• Starting from .
• Rewrite as .
• Comparing with the definition of inverse , we get:

Requirement: The modulus must be prime and .

Computation: We compute using fast modular exponentiation in time.

Example: Find the inverse of modulo .

• .
• .
• .
• Check: . ✓

So the inverse of modulo is .

For a square matrix of odd order , the middle row and middle column are well-defined and pass through the center element.

Conditions:

• The problem is typically defined for matrices of odd dimension (so a unique middle exists).
• Middle index (integer division, 0-based indexing).

Approach:

• Let mid = n / 2.
• Sum of middle row: add all elements for to .
• Sum of middle column: add all elements for to .
• The center element is counted in both; if a combined total is needed we subtract it once.

Formula:

Example: For matrix

• mid = 1.
• Middle row sum .
• Middle column sum .
• Combined (subtracting center 5): .

Time Complexity: .

Two arrays are circular rotations of each other if one can be obtained by rotating the other cyclically. We must verify this for every row against a reference row.

Key Idea (String Concatenation Trick):

• An array B is a rotation of array A if and only if B is a substring of A + A (A concatenated with itself).

Algorithm:

1. Take the first row as the reference and build a string S = row0 + row0 (concatenation, using a separator to avoid false matches).
2. For each subsequent row i:
   • Convert row[i] into a string pattern P.
   • Check if P is a substring of S using a pattern matching algorithm (e.g., KMP).
   • If P is not found, the rows are not all circular rotations — return false.
3. If all rows pass, return true.

Example: For matrix

• Reference doubled: 1 2 3 4 1 2 3 4.
• Row 2 4 1 2 3 — found as substring. ✓
• Row 3 3 4 1 2 — found as substring. ✓
• Result: true.

Time Complexity: using KMP, where = number of rows, = row length.

The Inclusion-Exclusion Principle (IEP) is a counting technique to find the size of the union of sets by adding sizes of individual sets and correcting for over-counted overlaps.

For Two Sets:

We subtract because elements in both are counted twice.

For Three Sets:

Intuition:

• Add all single sets.
• Subtract all pairwise intersections (removed double counting).
• Add back triple intersection (which was subtracted too many times).

Example: Count numbers from to divisible by or .

• Divisible by : .
• Divisible by : .
• Divisible by : .
• By IEP: .

So 67 numbers between 1 and 100 are divisible by 2 or 3.

The Pigeonhole Principle states:

If items are placed into containers and , then at least one container must hold more than one item.

Generalized Pigeonhole Principle:

If items are placed into containers, then at least one container holds at least items.

Application 1 — Duplicate elements:

• Among any people, at least two share the same birth month (since there are only months). By generalized form: .

Application 2 — Subarray with sum divisible by n:

• Given an array of integers, there always exists a non-empty contiguous subarray whose sum is divisible by .
• Reason: Consider prefix sums modulo . There are possible remainders . If any prefix is , that prefix works. Otherwise, we have prefixes mapped to non-zero remainders, so by pigeonhole two prefix sums share a remainder — their difference is a subarray divisible by .

The principle is powerful for existence proofs in combinatorics.

Naive Exponentiation:

• Computes by multiplying by itself times.
• Loop runs times: result *= a.
• Time Complexity: .

Exponentiation by Squaring:

• Uses the property for even and for odd .
• Reduces the exponent by half each step.
• Time Complexity: .

Comparison Table:

When to use each:

• Naive is fine for very small exponents (e.g., ) where simplicity matters.
• Squaring is preferred for large exponents ( up to ), cryptography, and modular exponentiation where speed is critical.

Example: For , naive needs ~ multiplications while squaring needs only ~.

The Extended Euclidean Algorithm finds integers and satisfying Bézout's identity:

Use for Inverse:

• If , then .
• Taking modulo : .
• Thus (adjusted to be positive) is the modular inverse of .
• Works for any modulus (not just primes), unlike Fermat's method.

Tracing for :

Step 1 — Euclidean division:

• → gcd = 1.

Step 2 — Back-substitution:

So for .

Step 3 — Adjust to positive: .

Check: . ✓

Therefore, .

Both are fundamental combinatorial principles but serve very different purposes.

Inclusion-Exclusion Principle (IEP):

• Purpose: To count the exact size of the union of overlapping sets.
• Nature: A precise counting/enumeration formula.
• Formula: (and extensions).
• Typical use: Counting numbers divisible by given factors, derangements, surjections, counting problems with 'at least one' conditions.

Pigeonhole Principle:

• Purpose: To prove existence — guarantees that some condition must hold.
• Nature: An existence argument, not a counting formula.
• Statement: If items go into boxes, some box has items.
• Typical use: Proving duplicates exist, subarray sum divisibility, collision arguments, guaranteeing patterns.

Comparison Table:

Summary: IEP tells us how many, while Pigeonhole tells us that something must exist.

Objective: Compute safely for large (up to ~) without overflow.

Pseudocode:

function mulmod(a, b, m):
result = 0
a = a % m
while b > 0:
if (b & 1) == 1: // if lowest bit of b is set
result = (result + a) % m
a = (2 * a) % m // double a under modulo
b = b >> 1 // halve b
return result

Step-by-step explanation:

• result = 0: accumulator for the final answer.
• a = a % m: reduce first so it stays within bounds.
• if b is odd: the current bit of contributes the current value of , so we add it to the result modulo .
• a = (2 * a) % m: shift to the next binary place (doubling), keeping it reduced.
• b = b >> 1: process the next bit of .

Principle: This mirrors binary multiplication:

Because we only ever add and double (never directly multiply large numbers), intermediate values stay below , avoiding overflow.

Time Complexity: .

We need where:

• = multiples of
• = multiples of
• = multiples of

Step 1 — Individual counts:

Step 2 — Pairwise intersections (LCMs):

Step 3 — Triple intersection:

Step 4 — Apply IEP:

Answer: 734 integers from to are divisible by , , or .

In modular arithmetic, we can reduce numbers by modulo at each intermediate step without affecting the final result. This is crucial to prevent overflow and keep numbers manageable.

Key Distributive Properties:

Addition:

Subtraction:

(The ensures the result stays non-negative.)

Multiplication:

Why it works:

• Any integer can be written as where .
• When combining numbers, the terms are multiples of and vanish under modulo.
• Hence only the remainders influence the final modular result.

Important Exception — Division:

• Division does not distribute directly: .
• Instead we must multiply by the modular multiplicative inverse: .

Example: , which equals . ✓

Claim: If we choose any integers from the set , then at least two of them are consecutive, and consecutive integers are always coprime.

Setup — Constructing the Pigeonholes:

• Partition the numbers into pairs of consecutive integers:

• This gives exactly pairs (pigeonholes).

Applying the Pigeonhole Principle:

• We are choosing numbers (pigeons) and placing them into pairs (pigeonholes).
• Since , by the Pigeonhole Principle at least one pair must contain both its numbers among our chosen set.
• Those two numbers are consecutive integers of the form and .

Consecutive integers are coprime:

• Suppose . Then divides their difference .
• Therefore , meaning and are coprime.

Conclusion: At least one pair of the chosen integers is coprime.

Example: From (), choosing any numbers, e.g., contains consecutive pair which is coprime.

Division in modular arithmetic cannot be done directly. We convert it into multiplication by the modular multiplicative inverse.

Step-by-Step Approach:

1. Understand the goal: , where is the modular inverse of .
2. Check condition: Since is prime and is not a multiple of , , so the inverse exists.
3. Compute inverse using Fermat's Little Theorem:
   
   Use fast modular exponentiation to compute this in .
4. Multiply: Compute .

Illustration — :

• Here , , (prime).
• Inverse of 5: .
  • So . Check: . ✓
• Result: .

Verification: , and . ✓

Modular exponentiation — computing efficiently — is the computational backbone of many public-key cryptosystems, most notably RSA.

Role in RSA:
RSA relies on modular exponentiation for both encryption and decryption:

• Key generation: Choose two large primes and , compute and . Select public exponent and private exponent such that (i.e., is the modular inverse of ).

• Encryption: Ciphertext .

• Decryption: Plaintext .

Why it is significant:

• Efficiency: Messages and keys involve numbers with hundreds of digits. Fast modular exponentiation () makes these operations feasible; naive methods would be impossible.
• Security (One-way function): Computing is easy, but reversing it (finding ) without the private key requires factoring into and — computationally infeasible for large . This asymmetry provides security.
• Modular inverse is used to derive the private key from .

Summary: Modular exponentiation enables the practical, fast, and secure operations that make RSA and similar cryptosystems possible. Without efficient exponentiation, public-key cryptography would not be viable.

Computing the sum of the middle row and column depends heavily on whether the matrix has odd or even dimensions.

Odd-order matrix ( odd):

• A unique middle exists at index (integer division).
• The center element lies on both the middle row and middle column.
• Sum formula:
  
• We subtract the center once to avoid double counting.

Even-order matrix ( even):

• There is no single middle row or column; two central rows/columns exist.
• Handling options:
  • Declare the operation undefined and return an error/zero.
  • Consider the two middle rows (indices and ) and two middle columns, summing all four.
• The expected behavior must be clearly defined by the problem statement.

Edge Cases:

• matrix: The single element is both the middle row and column; sum .
• Non-square matrix: 'Middle row' and 'middle column' may differ; usually the problem restricts to square matrices.
• Empty matrix: Return or flag as invalid.

Example ():

• ; middle row ; middle column .
• Combined .

Time Complexity: .