Maths Olympiad Prep

Library / /20 of 144

Number theory Difficulty 7.7 National olympiad, round 2 Find the answer

Determine all positive integers n2 n\geq 2 that satisfy the following condition: for all a a and b b relatively prime to n n we have ab(modn)if and only ifab1(modn).a \equiv b \pmod n\qquad\text{if and only if}\qquad ab\equiv 1 \pmod n.

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

Solution

To determine all positive integers n2 n \geq 2 that satisfy the given condition, we need to analyze when ab(modn) a \equiv b \pmod{n} if and only if ab1(modn) ab \equiv 1 \pmod{n} for all a a and b b that are relatively prime to n n .

### Step 1: Analyze the given condition

The problem requires:
- ab(modn) a \equiv b \pmod{n} if and only if ab1(modn) ab \equiv 1 \pmod{n} .

### Step 2: Translating the conditions

1. If Part: If ab(modn) a \equiv b \pmod{n} , then a=b+kn a = b + kn for some integer k k . So, ab1(modn) ab \equiv 1 \pmod{n} implies (b+kn)b1(modn) (b + kn)b \equiv 1 \pmod{n} .

2. Only If Part: If ab1(modn) ab \equiv 1 \pmod{n} , then there exists some integer x x such that ab=1+xn ab = 1 + xn . This situation implies ab(modn) a \equiv b \pmod{n} .

Consider using group theory concepts, including units modulo n n . The set of integers coprime with n n , under multiplication modulo n n , forms the **multiplicative group of units mod n n**, denoted by Zn \mathbb{Z}_n^* .

### Step 3: Conditions on the structure of Zn\mathbb{Z}_n^*

For both conditions to hold:
- Zn \mathbb{Z}_n^* forms a group where every element has its inverse to satisfy the divisors such that (ab)21(modn)(ab)^2 \equiv 1 \pmod{n}.
- Specifically, a21(modn) a^2 \equiv 1 \pmod{n} for all a a in Zn\mathbb{Z}_n^*, indicating that each element in Zn\mathbb{Z}_n^* is its own inverse.

### Step 4: Determine n n such that every unit in Zn\mathbb{Z}_n^* is its own inverse

To solve the problem, every element in Zn \mathbb{Z}_n^* must be its own inverse. This is equivalent to demanding that the group order must be a power of 2, as groups with elements all self-invertible are those isomorphic to elementary abelian 2-groups.

### Step 5: Identifying all eligible n n

From the conditions operating on Zn\mathbb{Z}_n^*, the integer n n can be characterized as the product of distinct prime powers where the ϕ(n)=2k \phi(n) = 2^k for some k k , and where each ϕ(piki) \phi(p_i^{k_i}) , remains power of two.

For n2 n \ge 2 , this includes n=2k(k1),2k3(k0) n = 2^k (k \geq 1), 2^k3 (k \geq 0) , resulting into:
- n=2,3,4,6,8,12,24 n = 2, 3, 4, 6, 8, 12, 24 .

Thus, the list of positive integers n2 n \geq 2 satisfying the conditions of the problem statement are:
2,3,4,6,8,12,24. \boxed{2, 3, 4, 6, 8, 12, 24}.

This completes the problem's solving process.

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.