Solving Remainder Problems

1. The Basics: What is a Remainder?

At its core, a remainder is what is "left over" after a division. This concept is formalized by the Euclidean Division Lemma, which you've likely encountered before.

When we divide an integer (the dividend) by another positive integer (the divisor), we get a quotient and a remainder. The relationship is:

For this to be unique, the remainder must be non-negative and strictly less than the divisor.

A key point from the reading is that if the dividend is smaller than the divisor, the remainder is the dividend itself. For example, the remainder when 5 is divided by 8 is 5.

2. The Negative Remainder Trick

While the formal definition of a remainder requires it to be positive, using the concept of a negative remainder can drastically simplify calculations.

A negative remainder tells us how much we would need to add to the dividend to make it perfectly divisible by the divisor.

Example: What is the remainder when 26 is divided by 9?

• Positive Remainder: The largest multiple of 9 less than 26 is 18 ($9\times 2$). So, the remainder is $26-18=8$.
• Negative Remainder: The smallest multiple of 9 greater than 26 is 27 ($9\times 3$). 26 is 1 short of 27. So, the negative remainder is -1.

You can always convert a negative remainder back to the correct positive one by adding the divisor:

In our example: $-1+9=8$.

The power of this technique becomes clear when we work with larger expressions. Let's explore this further.

As the article demonstrates, one of the most useful properties of remainders is that you can perform the arithmetic operations (addition, subtraction, multiplication) on the remainders themselves instead of on the large numbers.

Let Rem(N/D) denote the remainder when N is divided by D. Then:

• Rem((A × B) / D) = Rem((Rem(A/D) × Rem(B/D)) / D)
• Rem((A + B) / D) = Rem((Rem(A/D) + Rem(B/D)) / D)

3. Remainders of Large Powers

A very common CAT question involves finding the remainder of a large exponential expression, like $a^b/d$. Trying to calculate $a^b$ is impossible. We need smarter methods.

Method 1: Cyclicity

The remainders of powers of a number often repeat in a cycle. Your background in computer science might make you think of this as a property of the modulo operator (%).

Example: Find the remainder of $3^{83}$ divided by 7.

Let's find the pattern of remainders of powers of 3 when divided by 7:

• $3^1÷7\to \text{Rem}=3$
• $3^2=9;9÷7\to \text{Rem}=2$
• $3^3=27;27÷7\to \text{Rem}=6$
• $3^4=81;81÷7\to \text{Rem}=4$
• $3^5=243;243÷7\to \text{Rem}=5$
• $3^6=729;729÷7\to \text{Rem}=1$
• $3^7=3^6\times 3÷7\to \text{Rem}=(1\times 3)÷7=3$

The pattern of remainders is (3, 2, 6, 4, 5, 1). It repeats every 6 powers. The length of this cycle is 6.

To find the remainder for $3^{83}$, we need to find where in the cycle the 83rd power falls. We do this by finding the remainder of the exponent when divided by the cycle length:

• $83÷6\to \text{Rem}=5$.

This means the remainder of $3^{83}÷7$ will be the same as the 5th term in our cycle, which is 5.

Method 2: Key Theorems (Fermat's and Euler's)

For certain cases, we can use powerful theorems to find the remainder of 1, which simplifies the problem immensely.

• Fermat's Little Theorem: If $p$ is a prime number, and $a$ is an integer not divisible by $p$, then:
  $a^{p-1}\equiv 1(\mathrm{mod}p)$
  This means $a^{p-1}$ when divided by $p$ leaves a remainder of 1.

• Euler's Totient Theorem: This is a more general version. If $a$ and $m$ are coprime (their HCF is 1), then:
  $a^{\varphi (m)}\equiv 1(\mathrm{mod}m)$
  Here, $\varphi (m)$ (phi) is Euler's Totient Function, which counts the number of positive integers up to $m$ that are coprime to $m$.

  • If $m$ is a prime number, $\varphi (m)=m-1$ (which is why Euler's theorem becomes Fermat's).
  • If $m=p_1^k\times p_2^j\times \dots$, then $\varphi (m)=m\times (1-1/p_1)\times (1-1/p_2)\times \dots$

Example using Fermat's Theorem: Find the remainder when $2^{1003}$ is divided by 17.

1. Identify the theorem: The divisor is 17, which is a prime number. The base is 2, which is not divisible by 17. We can use Fermat's Little Theorem.
2. Apply the theorem: $a^{p-1}\equiv 1(\mathrm{mod}p)$ becomes $2^{17-1}\equiv 1(\mathrm{mod}17)$, so $2^{16}\equiv 1(\mathrm{mod}17)$.
3. Reduce the exponent: We need to express the exponent 1003 in terms of 16.
   • Divide 1003 by 16: $1003=16\times 62+11$.
4. Substitute and solve: $$2^{1003}=2^{16\times 62+11}=(2^{16}{)}^{62}\times 2^{11}$$ When we divide by 17, the remainder of $(2^{16}{)}^{62}$ is $1^{62}=1$.
   So, the problem reduces to finding the remainder of $1\times 2^{11}$ when divided by 17.
5. Calculate the final part:
   • We need to find Rem($2^{11}/17$). We know $2^4=16\equiv -1(\mathrm{mod}17)$.
   • $2^{11}=2^4\times 2^4\times 2^3=16\times 16\times 8$.
   • The remainder is Rem($(-1)\times (-1)\times 8)/17$) = Rem($8/17$) = 8.

4. An MCQ Shortcut

In a multiple-choice setting, sometimes you don't need to solve the problem completely. The properties of the numbers involved can help you eliminate incorrect options quickly.

The principle: If Dividend $D$ is a multiple of $k$ and Divisor $d$ is also a multiple of $k$, then the Remainder $R$ must also be a multiple of $k$.

• Why? Because $D=d\times Q+R$.
• If $D=k\times D^{\prime }$ and $d=k\times d^{\prime }$, then $k\times D^{\prime }=(k\times d^{\prime })\times Q+R$.
• This simplifies to $R=k\times D^{\prime }-k\times d^{\prime }\times Q=k\times (D^{\prime }-d^{\prime }Q)$.
• As you can see, $R$ must be a multiple of $k$.

This is a fantastic tool for eliminating answer choices that don't share a common factor with the dividend and divisor.

Conclusion

You've made it through a dense but very important topic. Mastering remainders is not just about memorizing formulas, but about understanding the underlying properties of numbers to choose the right tool for the problem at hand.

Key Takeaways:

• Negative Remainders: Use them to simplify calculations, especially with multiplication. Remember to convert back to a positive remainder at the end ($R_{pos}=R_{neg}+\text{Divisor}$).
• Remainder of Expressions: You can work with the remainders of individual terms instead of the full numbers.
• Large Powers: Your first line of attack should be finding the cyclicity of remainders. If the divisor is prime, Fermat's Little Theorem is a powerful shortcut. If the divisor is composite, Euler's Theorem is your go-to.
• MCQ Hack: Always check if the dividend and divisor share a common factor. If they do, the remainder must also have that factor, which can help you eliminate options instantly.

In our next lesson, we will continue exploring the properties of numbers by learning how to calculate the number of factors, the sum of all factors, and the product of all factors of a given number. This builds on the prime factorization skills we've been using and is another key area for CAT questions. Keep practicing