Mid Term Exam 1 (14th Batch) — Full Solution

Four questions, 2.5 marks each — modular arithmetic, linear congruences, and queueing theory (M/M/1, M/M/∞).

Question 1 — Modular Arithmetic in Z14

Construct a table for $a = 1$ to $13$ in $\mathbb{Z}_{14}$, compute $\gcd(a, 14)$, and identify all invertible elements. Then find their inverses.

Concept Needed

An element $a \in \mathbb{Z}_n$ is called invertible (a unit) if there exists $b \in \mathbb{Z}_n$ such that

$a \cdot b \equiv 1 \pmod{n}$

Here $n = 14 = 2 \times 7$. So any $a$ that shares a factor of $2$ or $7$ with $14$ will not be invertible.

Step 1: Build the GCD Table

Step 2: List of Invertible Elements

From the table, the invertible elements (units) of $\mathbb{Z}_{14}$ are:

$U(14) = \{1, 3, 5, 9, 11, 13\}$

Check with Euler's totient function:

$\phi(14) = \phi(2) \times \phi(7) = 1 \times 6 = 6$

This matches — we found exactly $6$ invertible elements. This is a good way to verify your answer in the exam.

Step 3: Find Each Inverse (Sample Working)

We find $b$ such that $a \cdot b \equiv 1 \pmod{14}$, by trying small values.

• $a = 1$: $1 \times 1 = 1 \equiv 1 \Rightarrow 1^{-1} = 1$
• $a = 3$: $3 \times 5 = 15 \equiv 1 \Rightarrow 3^{-1} = 5$
• $a = 5$: $5 \times 3 = 15 \equiv 1 \Rightarrow 5^{-1} = 3$
• $a = 9$: $9 \times 11 = 99 = 7(14) + 1 \equiv 1 \Rightarrow 9^{-1} = 11$
• $a = 11$: $11 \times 9 = 99 \equiv 1 \Rightarrow 11^{-1} = 9$
• $a = 13$: $13 \times 13 = 169 = 12(14) + 1 \equiv 1 \Rightarrow 13^{-1} = 13$ — note that $13 \equiv -1 \pmod{14}$, and $(-1) \times (-1) = 1$, so it is its own inverse, a useful shortcut.

Question 2 — Linear Congruence

Solve: $8x + 6 \equiv 4 \pmod{15}$

Formula / Rule

For $ax \equiv b \pmod{n}$ with $\gcd(a,n)=1$, the solution is unique modulo $n$ and is given by

$x \equiv a^{-1} b \pmod n$

Step 1: Simplify the Congruence

$8x + 6 \equiv 4 \pmod{15}$

$8x \equiv 4 - 6 \pmod{15}$

$8x \equiv -2 \pmod{15}$

Since $-2 \equiv 13 \pmod{15}$:

$8x \equiv 13 \pmod{15}$

Step 2: Check that a Unique Solution Exists

$\gcd(8, 15) = 1$

Since the gcd is $1$, a unique solution modulo $15$ exists.

Step 3: Find the Inverse of 8 modulo 15

Try small multiples of $8$:

$8 \times 2 = 16 \equiv 1 \pmod{15}$

So,

$8^{-1} \equiv 2 \pmod{15}$

Step 4: Multiply Both Sides by the Inverse

$x \equiv 2 \times 13 \pmod{15}$

$x \equiv 26 \pmod{15}$

$x \equiv 11 \pmod{15}$

Verification

Substitute $x = 11$ back into the original congruence:

$8(11) + 6 = 88 + 6 = 94$

$94 = 6 \times 15 + 4 \ \Rightarrow\ 94 \equiv 4 \pmod{15}$

This matches the right-hand side, so the answer is verified correct.

Question 3 — Queueing Theory: M/M/1 System with Service Level Requirement

A service center receives customers according to a Poisson process with mean interarrival time of 5 minutes. The service time is exponentially distributed. Management requires that:

1. $P(\text{number of customers in system} > 3) < 0.1$
2. Find the maximum allowable mean service time.
3. Compute the expected waiting time in the queue.

Concept Needed: The M/M/1 Queue

• Arrivals follow a Poisson process with rate $\lambda$.
• Service times are exponentially distributed with rate $\mu$.
• One single server, unlimited queue capacity (M/M/1 model).
• Traffic intensity: $\rho = \lambda / \mu$, and the system is stable only if $\rho < 1$.

$P(N > n) = \rho^{\,n+1}$

Given

• Mean interarrival time $= 5$ minutes $\Rightarrow \lambda = \dfrac{1}{5} = 0.2$ customers/min
• Requirement: $P(N > 3) < 0.1$

Part (i): Setting Up the Inequality

Using $P(N>n) = \rho^{n+1}$ with $n = 3$:

$P(N>3) = \rho^{4} < 0.1$

Part (ii): Maximum Allowable Mean Service Time

Step 1: Solve for maximum $\rho$

$\rho^4 < 0.1$

$\rho < (0.1)^{1/4}$

$\rho < 0.5623 \quad \text{(taking 4 decimal places)}$

Step 2: Solve for minimum $\mu$

$\rho = \frac{\lambda}{\mu} \ \Rightarrow\ \mu > \frac{\lambda}{\rho_{max}} = \frac{0.2}{0.5623}$

$\mu > 0.3557 \text{ customers/min}$

Step 3: Convert to Mean Service Time

Mean service time $= \dfrac{1}{\mu}$. Since $\mu$ must be greater than $0.3557$, the mean service time must be less than:

$\frac{1}{\mu} < \frac{1}{0.3557} \approx 2.812 \text{ minutes}$

Part (iii): Expected Waiting Time in Queue

$W_q = \frac{\lambda}{\mu(\mu - \lambda)} = \frac{\rho}{\mu - \lambda}$

Using the boundary (maximum allowed) values from Part (ii), $\mu = 0.3557$ per min and $\lambda = 0.2$ per min:

Step 1: Compute $\mu - \lambda$

$\mu - \lambda = 0.3557 - 0.2 = 0.1557$

Step 2: Substitute into the formula

$W_q = \frac{0.2}{0.3557 \times 0.1557} = \frac{0.2}{0.0554}$

$W_q \approx 3.61 \text{ minutes}$

Question 4 — Queueing Theory: M/M/∞ System

A system has infinite servers (M/M/∞). Customers arrive at rate 6 per hour, and service rate per server is 3 per hour. Find the probability that there are more than 4 customers in the system.

Concept Needed: The M/M/∞ Model

• Every arriving customer gets its own server immediately — there is no queue and no waiting.
• Arrivals: Poisson with rate $\lambda$. Each server: exponential service with rate $\mu$.
• The number of customers in the system, $N$, follows a Poisson distribution with mean $a = \lambda / \mu$.

Given

• Arrival rate: $\lambda = 6$ customers/hour
• Service rate per server: $\mu = 3$ customers/hour

Required

$P(N > 4) = ?$

$a = \frac{\lambda}{\mu}, \qquad P(N=n) = \frac{e^{-a}a^{n}}{n!}, \qquad P(N>4) = 1 - \sum_{n=0}^{4} P(N=n)$

Step 1: Compute the Mean $a$

$a = \frac{\lambda}{\mu} = \frac{6}{3} = 2$

Step 2: Compute $P(N=n)$ for $n = 0$ to $4$

Step 3: Sum the Probabilities

$\sum_{n=0}^{4} P(N=n) = 0.1353+0.2707+0.2707+0.1804+0.0902 = 0.9473$

Step 4: Compute $P(N>4)$

$P(N>4) = 1 - 0.9473 = 0.0527$

Interview Corner