Number System — Advanced Exam Problems

🎯 Learning Objective

Beat the hardest number-system patterns — giant power remainders, or-counting and LCM remainder families.

💡 Concept

• Big-power remainders: rewrite the base as (divisor ± 1) or use small cycles — never expand the power
• Odd powers of −1 leave a NEGATIVE remainder — add the divisor back to land in range
• Counting 'divisible by a or b' in a range = n/a + n/b − n/LCM (inclusion-exclusion)
• Same remainder r with several divisors → the number lives in the family k × LCM + r
• Extra conditions (also divisible by 7) → walk the family members one by one and test

🧮 Key Formulas

(d − 1)^even ÷ d → remainder 1; (d − 1)^odd ÷ d → remainder d − 1

>

Count divisible by a or b = ⌊n/a⌋ + ⌊n/b⌋ − ⌊n/LCM⌋

>

Same remainder r → N = k × LCM(divisors) + r

✏️ Easy Example

Q. Find the largest 3-digit number that is exactly divisible by 8, 10 and 12.

1. A number divisible by all three must be a multiple of LCM(8, 10, 12) = 120
2. Largest 3-digit number = 999; divide: 999 ÷ 120 = 8 remainder 39
3. Strip the remainder: 999 − 39 = 960 — the 8th multiple of 120

Answer: 960

🇮🇳 Real-Life Example

Cryptography and OTP systems run entirely on remainders of giant powers — the same minus-one trick, scaled up.

📝 Exam-Level Example

Q. Find the remainder when 17^200 is divided by 18.

1. Dividing 17 by 18 leaves remainder 17 — but 17 = 18 − 1, so treat it as −1 (one short of a full group)
2. Then 17^200 behaves exactly like (−1)^200 as far as remainders by 18 are concerned
3. (−1)^200 = +1 because 200 is even — the minus signs pair up and cancel
4. +1 is already a valid remainder (0 ≤ 1 < 18), so no adjustment is needed
5. Remainder = 1

Answer: 1

📝 Exam-Level Example

Q. How many numbers from 1 to 300 are divisible by 3 or 5?

1. Count by 3: ⌊300/3⌋ = 100 numbers; count by 5: ⌊300/5⌋ = 60 numbers
2. Adding gives 160, but multiples of BOTH (15, 30, 45 …) have been counted twice
3. Count by 15 (the LCM of 3 and 5): ⌊300/15⌋ = 20
4. Subtract the double-counted ones once: 100 + 60 − 20
5. = 140 numbers

Answer: 140

📝 Exam-Level Example

Q. Find the least number which when divided by 12, 16 and 24 leaves remainder 5 in each case, and which is exactly divisible by 7.

1. Same remainder 5 with every divisor → the number = (common multiple of 12, 16, 24) + 5
2. LCM(12, 16, 24) = 48, so the number has the form 48k + 5
3. It must also divide by 7 — test the family members: k = 1, 2, 3, 4, 5 give 53, 101, 149, 197, 245
4. Check each by 7: 53, 101, 149, 197 all fail; 245 = 7 × 35 works
5. Least such number = 245

Answer: 245

🪄 Memory Trick

Divisor-neighbour trick: base one LESS than the divisor → call it −1; one MORE → call it +1. 17^200 ÷ 18 → (−1)^200 → 1, in five seconds.

⚠️ Common Mistakes

• ❌ Leaving a negative remainder as the final answer — convert −r to (divisor − r) at the end
• ❌ Adding the by-3 and by-5 counts without removing the by-15 overlap
• ❌ Writing 'LCM − 5' instead of 'LCM + 5' when remainder 5 is left in each case

🏆 Exam Tips

• ✅ Same remainder r with many divisors → number = k × LCM + r, always
• ✅ 'Divisible by a or b' → n/a + n/b − n/LCM, one line
• ✅ Odd power of −1 → negative remainder → add the divisor back

📌 Summary

• Neighbour bases (−1/+1) crush big-power remainders
• Or-counting needs inclusion-exclusion via the LCM
• Same remainder r → LCM family + r; extra condition → test members
• Always return remainders to the 0 to d−1 range