Understanding remainders and cyclicity is fundamental for excelling in the quantitative aptitude sections of competitive exams like the CAT. This module will equip you with the core concepts and techniques to efficiently solve problems involving division and repeating patterns.

When an integer 'a' is divided by a positive integer 'n', we get a quotient 'q' and a remainder 'r'. This relationship is expressed as: a = nq + r, where 0 ≤ r < n. The remainder 'r' is the amount 'left over' after dividing 'a' into as many whole groups of 'n' as possible. For example, when 17 is divided by 5, 17 = 5 * 3 + 2. Here, the remainder is 2.

Several properties simplify remainder calculations:

1. Sum of Remainders: (a + b) mod n = ((a mod n) + (b mod n)) mod n
2. Product of Remainders: (a * b) mod n = ((a mod n) * (b mod n)) mod n
3. Difference of Remainders: (a - b) mod n = ((a mod n) - (b mod n) + n) mod n (adding 'n' ensures a positive remainder)
4. Power of Remainders: a^k mod n = (a mod n)^k mod n

Cyclicity refers to the repeating pattern of remainders when powers of a number are divided by a fixed divisor. For instance, consider powers of 2 divided by 5: 2^1 mod 5 = 2 2^2 mod 5 = 4 2^3 mod 5 = 8 mod 5 = 3 2^4 mod 5 = 16 mod 5 = 1 2^5 mod 5 = 32 mod 5 = 2

The remainders (2, 4, 3, 1) repeat every 4 powers. The cycle length is 4. To find the remainder of 2^100 divided by 5, we look at the exponent modulo the cycle length: 100 mod 4 = 0. Since the cycle starts with the 1st power, an exponent that is a multiple of the cycle length corresponds to the last element in the cycle (which is 1 in this case).

The cycle length for powers of a number 'a' modulo 'n' depends on 'a' and 'n'. Common cycle lengths for the last digit of powers (which is equivalent to modulo 10) are:

• Powers of 2: Cycle length 4 (2, 4, 8, 6)
• Powers of 3: Cycle length 4 (3, 9, 7, 1)
• Powers of 4: Cycle length 2 (4, 6)
• Powers of 7: Cycle length 4 (7, 9, 3, 1)
• Powers of 8: Cycle length 4 (8, 4, 2, 6)
• Powers of 9: Cycle length 2 (9, 1)

For other bases and moduli, you might need to calculate the first few powers until a remainder repeats. A key theorem, Euler's Totient Theorem, provides a more advanced way to determine cycle lengths, stating that a^φ(n) ≡ 1 (mod n) if gcd(a, n) = 1, where φ(n) is Euler's totient function.

To find the remainder of a^k mod n:

1. Determine the cycle length (let's call it 'c') for powers of 'a' modulo 'n'.
2. Calculate the effective exponent by finding k mod c. If k mod c is 0, use 'c' as the exponent (unless the cycle starts from 0, which is rare for powers).
3. Calculate a^(effective exponent) mod n. This will be your answer.

When the base and modulus are not coprime (i.e., gcd(a, n) > 1), direct application of Euler's theorem is not possible. In such cases, you might need to break down the modulus or use specific properties. For instance, finding the remainder of 2^100 divided by 6. Since gcd(2, 6) = 2, we can't directly use cycle length 4. However, for powers of 2 greater than or equal to 2, 2^k mod 6 will always be 4 (2^2=4, 2^3=8 mod 6 = 2, 2^4=16 mod 6 = 4, 2^5=32 mod 6 = 2... wait, this is incorrect. Let's re-evaluate: 2^1 mod 6 = 2, 2^2 mod 6 = 4, 2^3 mod 6 = 8 mod 6 = 2, 2^4 mod 6 = 16 mod 6 = 4. The cycle is 2, 4 with length 2 for powers >= 1. So 2^100 mod 6 would be 4. A more robust method for non-coprime cases involves Chinese Remainder Theorem or analyzing the prime factorization of the modulus.