Problem #64 HARD
The Stolen Sapphire
Scenario Number Theory Modular Arithmetic Deduction
Problem Statement
Inspector Varsha of the Jaipur CID is called to the Gem Palace hotel, where a priceless blue sapphire has been stolen from room 417. The hotel has exactly 100 rooms, numbered 1 to 100.
The front desk log shows that four guests checked out this morning: the guests from rooms 17, 34, 51, and 82.
A witness reports seeing someone leaving room 417 — but the hotel only has floors 1 to 4 with rooms 1 to 25 on each floor. Room 417 does not exist.
Varsha ignores the room number and focuses on the four guests. Her informant whispers: 'The thief's room number is a multiple of 17. When you square the room number and divide by 7, the remainder is 4. The room number is not prime.'
Varsha looks at her list of four suspects: rooms 17, 34, 51, 82. She narrows it down in under a minute.
Which room number belongs to the thief? The room number must be: a multiple of 17, produce a remainder of 4 when its square is divided by 7, and not be a prime number.
Answer & Quick Explanation
Think you've got it? Click below to check your answer.
Room 51 is the primary answer (smallest valid candidate). Both 51 and 82 satisfy all constraints: multiple of 17, not prime, and n² ≡ 4 (mod 7). Room 34 fails the modular test (34² mod 7 = 1). Room 17 is eliminated as prime. Inspector Varsha's key technique: compute n mod 7 first, then square it.
Detailed Editorial Solution
Want to see the step-by-step breakdown? Click below to reveal the editorial.
Work through each constraint systematically for all four candidates. Modular arithmetic on squares is efficiently done by first reducing the base mod 7, then squaring the result.
Step 1: Candidates: 17, 34, 51, 82. All are multiples of 17 ✓.
Step 2: Primality check: 17 is prime → eliminate. 34 = 2×17 (not prime ✓). 51 = 3×17 (not prime ✓). 82 = 2×41 (not prime ✓). Remaining: 34, 51, 82.
Step 3: Compute n² mod 7 for each: use (n mod 7)² mod 7.
Step 4: 34 mod 7 = 34 − 4×7 = 34 − 28 = 6. 6² = 36. 36 mod 7 = 36 − 5×7 = 1. So 34² mod 7 = 1 ≠ 4. Eliminate 34.
Step 5: 51 mod 7 = 51 − 7×7 = 51 − 49 = 2. 2² = 4. 4 mod 7 = 4. So 51² mod 7 = 4 ✓.
Step 6: 82 mod 7 = 82 − 11×7 = 82 − 77 = 5. 5² = 25. 25 mod 7 = 25 − 3×7 = 4. So 82² mod 7 = 4 ✓. Both 51 and 82 satisfy all stated constraints.
Key Insight:
Computing n² mod m directly for large n is tedious. The shortcut is always to first reduce n mod m, then square the result and reduce again. This is because (n mod m)² mod m = n² mod m — modular arithmetic distributes over multiplication. This technique appears constantly in cryptography and competitive programming.