IMO 1990 SL 21

Problem

(ROM 1′) Let n be a composite natural number and p a proper divisor of n. Find the binary representation of the smallest natural number N such that (1+2p+2n−p)N−1 2n is an integer.

Solution

We must solve the congruence (1 + 2p + 2n−p)N \equiv1 (mod 2n). Since (1 + 2p + 2n−p) and 2n are coprime, there clearly exists a unique N satisfying this equation and 0 < N < 2n. Let us assume n = mp. Then we have (1 + 2p) m−1 j=0 (−1)j2jp \equiv 1 (mod 2n) and (1 + 2n−p)(1 −2n−p) \equiv1 (mod 2n). By multiplying the two congruences we obtain (1 + 2p)(1 + 2n−p)(1 −2n−p) ⎛ ⎝ m−1  j=0 (−1)j2jp ⎞ ⎠\equiv1 (mod 2n) . Since (1 + 2p)(1 + 2n−p) \equiv(1 + 2p + 2n−p) (mod 2n), it follows that N \equiv (1−2n−p) m−1 j=0 (−1)j2jp (mod 2n). The integer N = m−1 j=0 (−1)j2jp− 2n−p + 2n satisfies the congruence and 0 < N \leq2n. Using that for a > b we have in binary representation 2a −2b = 11 . . .11    a−b times 00 . . . 00    b times , the binary representation of N is calculated as follows: N = ⎧ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎩ 11 . . .11    p times 11 . . . 11    p times 00 . . .00    p times . . . 11 . . .11    p times 00 . . . 00    p−1 times 1, 2 ∤n p , 11 . . .11    p−1 times 00 . . .00    p+1 times 11 . . .11    p times 00 . . . 00    p times . . . 11 . . . 11    p times 00 . . .00    p−1 times 1, 2 | n p .