Maths Olympiad Prep

Library / /16 of 37

Algebra Difficulty 7.8 National olympiad, round 2 Find the answer

Let Z/nZ\mathbb{Z}/n\mathbb{Z} denote the set of integers considered modulo nn (hence Z/nZ\mathbb{Z}/n\mathbb{Z} has nn elements). Find all positive integers nn for which there exists a bijective function g:Z/nZZ/nZg: \mathbb{Z}/n\mathbb{Z} \to \mathbb{Z}/n\mathbb{Z}, such that the 101 functions
g(x),g(x)+x,g(x)+2x,,g(x)+100xg(x), \quad g(x) + x, \quad g(x) + 2x, \quad \dots, \quad g(x) + 100x
are all bijections on Z/nZ\mathbb{Z}/n\mathbb{Z}.

[i]Ashwin Sah and Yang Liu[/i]

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

Solution

Let Z/nZ\mathbb{Z}/n\mathbb{Z} denote the set of integers considered modulo nn. We need to find all positive integers nn for which there exists a bijective function g:Z/nZZ/nZg: \mathbb{Z}/n\mathbb{Z} \to \mathbb{Z}/n\mathbb{Z}, such that the 101 functions
g(x),g(x)+x,g(x)+2x,,g(x)+100xg(x), \quad g(x) + x, \quad g(x) + 2x, \quad \dots, \quad g(x) + 100x
are all bijections on Z/nZ\mathbb{Z}/n\mathbb{Z}.

We claim that the answer is all numbers relatively prime to 101!101!. The construction is to let gg be the identity function.

To prove this, we need to show that if nn is relatively prime to 101!101!, then such a bijective function gg exists. Conversely, if nn shares a common factor with 101!101!, then no such bijective function gg can exist.

### Proof:
1. **Existence for nn relatively prime to 101!101!:**
- Let g(x)=xg(x) = x. Then the functions g(x)+kx=(k+1)xg(x) + kx = (k+1)x for k=0,1,,100k = 0, 1, \ldots, 100 are all bijections if (k+1)(k+1) is invertible modulo nn. Since nn is relatively prime to 101!101!, all integers from 1 to 101 are invertible modulo nn. Therefore, each function g(x)+kxg(x) + kx is a bijection.

2. **Non-existence for nn not relatively prime to 101!101!:**
- Suppose nn has a prime factor p101p \leq 101. Consider the sum of the functions g(x)+kxg(x) + kx over all xZ/nZx \in \mathbb{Z}/n\mathbb{Z}. By properties of bijections, this sum must be congruent modulo nn. However, if pp divides nn, then the sums of powers of xx modulo nn will not satisfy the necessary conditions for all kk, leading to a contradiction.

Thus, the positive integers nn for which there exists a bijective function g:Z/nZZ/nZg: \mathbb{Z}/n\mathbb{Z} \to \mathbb{Z}/n\mathbb{Z} such that the 101 functions g(x),g(x)+x,g(x)+2x,,g(x)+100xg(x), g(x) + x, g(x) + 2x, \ldots, g(x) + 100x are all bijections are exactly those integers nn that are relatively prime to 101!101!.

The answer is: All positive integers n relatively prime to 101!\boxed{\text{All positive integers } n \text{ relatively prime to } 101!}.

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.