Maths Olympiad Prep

Library / /97 of 520

Number theory Difficulty 6.5 National olympiad Find the answer

Determine all positive integers nn such that xy+10  (modn) xy+1 \equiv 0 \; \pmod{n} implies that x+y0  (modn) x+y \equiv 0 \; \pmod{n}.

A number or a short expression. Spacing and $ signs are ignored.

Solution

To determine all positive integers n n such that xy+10(modn) xy + 1 \equiv 0 \pmod{n} implies x+y0(modn) x + y \equiv 0 \pmod{n} , we proceed as follows:

1. **Assume xy+10(modn) xy + 1 \equiv 0 \pmod{n} **:
xy1(modn) xy \equiv -1 \pmod{n}

2. **Consider x x and y y such that x x is coprime to n n **:
Since x x is coprime to n n , there exists an integer x1 x^{-1} such that:
xx11(modn) x x^{-1} \equiv 1 \pmod{n}

3. **Express y y in terms of x x **:
From xy1(modn) xy \equiv -1 \pmod{n} , multiply both sides by x1 x^{-1} :
yx1(modn) y \equiv -x^{-1} \pmod{n}

4. **Check the condition x+y0(modn) x + y \equiv 0 \pmod{n} **:
Substitute y y from the previous step:
x+yxx10(modn) x + y \equiv x - x^{-1} \equiv 0 \pmod{n}
This implies:
xx1(modn) x \equiv x^{-1} \pmod{n}

5. **Analyze the implications of xx1(modn) x \equiv x^{-1} \pmod{n} **:
This means x21(modn) x^2 \equiv 1 \pmod{n} . Therefore, x x must be a solution to the equation:
x210(modn) x^2 - 1 \equiv 0 \pmod{n}
(x1)(x+1)0(modn) (x - 1)(x + 1) \equiv 0 \pmod{n}

6. **Determine the structure of n n **:
For the above equation to hold for all x x coprime to n n , n n must be such that every x x coprime to n n satisfies x21(modn) x^2 \equiv 1 \pmod{n} . This is true if and only if n n is a product of distinct primes, specifically n=2 n = 2 .

7. **Verify n=2 n = 2 **:
If n=2 n = 2 , then:
xy+10(mod2)    xy11(mod2) xy + 1 \equiv 0 \pmod{2} \implies xy \equiv -1 \equiv 1 \pmod{2}
Since x x and y y are integers, x x and y y must both be odd, and thus:
x+y1+10(mod2) x + y \equiv 1 + 1 \equiv 0 \pmod{2}
This satisfies the condition x+y0(mod2) x + y \equiv 0 \pmod{2} .

Therefore, the only positive integer n n that satisfies the given condition is n=2 n = 2 .

The final answer is 2 \boxed{2} .

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.