Indeed, it's quite easy: It says that the inverse of any $a$ in $\mathbb Z_n$ is actually $a$. This means that in the group $U(\mathbb Z_n)$ each element has order $2$. It's easy to see that unless $n$ is $1,2,3,4$, we will be able to find a number which is coprime with $n$, $>1$ and $<\sqrt n$. That's because if $n$ is prime we take $2$ and if $n$ isn't prime we take $p-1$, where $p$ is the smallest prime factor of $n$. Edit: Looks like I keep missing cases : if $2|n$ then this might not work; Anyway, we know that $\phi(n)$ must be a power of $2$, which tells us that $n$ has form $2^tp_1p_2\ldots p_k$, with $p_i$ odd primes of the form $2^a+1$. Morevoer, we know that there are no numbers $a$ s.t. $(a,n)=1$ and $1<a\le\sqrt n$. I'll see what I can do.

I may be wrong, but I think that grobber is wrong. I don't this are the answers. And I wouldnt call it exactly very easy number theory. As far as I remember this problem was given in a TST in Hungary, it also appeared on IMO Shortlist and finally a more general case was given in our TST this year (and contrary to most peoples expectations, it didnt turn out to be easy). It isnt difficult, but not very easy.

Do you by any chance know what the answer is?

Answer: 1,2,3,4,6,8,12,24.

Huh, sorry, I must have been wrong... darij

I'm terribly sorry I rushed into it like that. Ok, so after the above observations, the proof isn't hard to come by: if $n\ge 49$ then we take $a=7$. $7$ doesn't divide $n$ because it's not a Fermat prime, and $1<7\le\sqrt n$. On the other hand, if $n\ge 25$, then $30=2\cdot 3\cdot 5|n$. This means that the only number $>25$ that we have to check is $30$, and it doesn't work because we take $a=7$ again. The solutions can now be found manually.

I think Harazi means that one : http://www.kalva.demon.co.uk/short/soln/sh00n1.html Pierre.

Yes, I rushed a little bit, but it's practically the same problem. Anyway, what's with these complicated solutions? The solution given by Sasha to my problem for the TST is just perfect: smart and very short.

ab+1 divides n isn't the same as ab = 1 mod n...

Really? Well, Peter, when I said they are practically the same I wasn't wrong. Think a little bit: they both ask the numbers n for which any relatively prime a with n has order 2 in Z_n? Isn't this the same?

harazi wrote: they both ask the numbers n for which any relatively prime a with n has order 2 in Z_n? Isn't this the same? Sorry hazari, I just learnt the euler phi function yesterday, orders are planned for in a couple of days, currently I got even no clue what they are

Peter VDD wrote: ab+1 divides n isn't the same as ab = 1 mod n... He replaced b by -b. Then, of course, the condition "ab + 1 is divisible by n" becomes "ab = 1 mod n", and the condition "a + b is divisible by n" becomes "a = b mod n". Darij

Yes, sorry didn't think of that since both problems state natural numbers

Sorry, of course I meant: replace b by any number equivalent to -b modulo n. This number needs not to be negative. Darij

what was the problem in your test Harazi?

A solution using the (well known ) $si$-formula (si stands for self-inverse): Define $\mathrm{si}_k \left( n \right) := \left| \left\{ x \in \mathbb{Z}_n \mid x^k = 1 \right\} \right|$ then you get $\gcd(x,y)=1 \implies \\ \mathrm{si}_k \left( xy \right) = \mathrm{si}_k \left( x \right) \mathrm{si}_k \left( y \right) \\ \mathrm{si}_{xy} \left( n \right) = \mathrm{si}_x \left( n \right) \mathrm{si}_y \left( n \right)$ and $\mathrm{si}_k \left( p^n \right) = \gcd \left( k,p-1 \right)$ for every odd prime $p$ and additional: if $k$ is odd, then $\mathrm{si}_k \left( 2^n \right) = 1$ if $k$ is even, then $\mathrm{si}_k \left( 2^n \right) = 2^m$ where $2^m || \gcd (2k,2^{n-1})$ (I hope I wrote all properties correct) I will only need the case $k=2$, so I will only prove this case, the rest is for your training - multiplicativity follows directly from chinese remainder theorem - $\mathrm{si}_2 \left( p^n \right) = 2 $ for every odd prime $p$: this follows easily from the fact that $x^2 \equiv 1 \mod p^n \iff p^n | (x-1)(x+1)$, so there are exactly two solutions - $\mathrm{si}_2 \left( 2 \right) = 1$ and $\mathrm{si}_2 \left( 4 \right) = 2$ can easily be checked, so only $\mathrm{si}_2 \left( 2^n \right) = 4$ for $n\geq 3$ remains to show: $x^2 \equiv 1 \mod 2^n \iff 2^n | (x-1)(x+1) \iff 2^{n-1} | x-1 $ or $2^{n-1} | x+1$, which immediatly gives the desired result all we want to find are the solutions of $\mathrm{si}_2 \left( n \right) = \phi (n)$, and using multiplicativity reduces it to find all powers $p^n$ of primes that fulfill it. The case $p=2$ is also easy checked, and since $\mathrm{si}_2 \left( p^n \right)=2$ for all odd primes, you get that only the case $p=3,n=1$ is possible. So all solutions are found.

I think that this problem can be solved slightly more easier. First of all, if we have a prime $ p $, and positive integer $ k \geqslant 1 $ and an element $ a \in (\mathbb{Z}_{p^{k}})^{*} $, such that $ a^{2} = 1 $ then $ p^{k} | (a-1)(a+1) $, so there are $ i,j \geqslant 0 $ integers such that $ i+j = k $ and $ p^{i} | a-1 $ and $ p^{j} | a+1 $. Therefore $ p^{ min(i,j) } | 2 $. So in the case of $ p > 2 $ we get that $ min(i,j) = 0 $ and in the case of $ p = 2 $ we get that $ min(i,j) = 0 $ or $ 1 $. From this it is easy to see that in the case of $ p>2 $ we have that the only elements of $ (\mathbb{Z}_{p^{k}})^{*} $ of order $ 2 $ are $ 1,-1 $, and for $ p = 2 $, $ k \geqslant 3 $ we have that they are $ 1,-1,2^{k-1}-1,2^{k-1}+1 $. So if we have that for every element $ a \in (\mathbb{Z}_{p^{k}})^{*} $, that $ a^{2} = 1 $ then in the case $ p > 2 $ we have $ \varphi(p^{k}) = p^{k-1}(p-1) = 2 $, so the only case is $ p = 3 $, $ k = 1 $, and when $ p = 2 $, for $ k=1,2,3 $ it is easy to see that this is satisfied, but for $ k > 3 $, $ \varphi(2^{k}) = 2^{k-1} > 4 $. Now if $ n = p_{1}^{k_{1}} p_{2}^{k_{2}} p_{3}^{k_{3}} \ldots p_{m}^{k_{m}} $ satisfies the conditions of the problem, then if we take some $ 1 \leqslant j \leqslant m $, then we have an epimorphism $ ( \mathbb{Z}_{n} )^{*} \rightarrow ( \mathbb{Z}_{p_{j}^{k_{j}}} )^{*} $, so if for every $ a \in ( \mathbb{Z}_{n} )^{*} $ we have that $ a^{2} = 1 $, then of course for every $ a \in ( \mathbb{Z}_{p_{j}^{k_{j}}} )^{*} $ we have that $ a^{2} = 1 $, so, as we have seen, $ p_{j} $ is or $ 2 $ either $ 3 $ and in the case $ p_{j} = 2 $ we have $ 1 \leqslant k_{j} \leqslant 3 $ and for $ p_{j} = 3 $ we have $ k_{j} = 1 $. So the only options are $ n=2,3,8,3,6,12,24 $, and it is easy to see that they satisfy the property of the problem.

Oups . I am very sorry, ZetaX, I didn't see your solution, I looked only on page 1.

Leva, here is another nice and easy number theory problem from you, started from this problem and given in TST 2004 in Romania: Let $n,m$ such that $ a^m-1$ is divisible by $n$ for any positive integer $a$ smaller than $n$ and relatively prime to $n$. Then $n\leq 4m(2^m-1)$ It would be very nice if you found a better estimation. [Moderator edit: This Romanian TST problem is being discussed on http://www.artofproblemsolving.com/Forum/viewtopic.php?f=56&t=359205 and http://www.artofproblemsolving.com/Forum/viewtopic.php?p=19483 . More precisely, the TST problem has an additional assumption that $m\geq 2$, and requires that all positive integers $a$ coprime to $n$ satisfy $n\mid a^m-1$ (instead of only those smaller than $n$), but is easily seen to be equivalent to the problem above.]

A nice and standard one. Notice that suppose we have $a \equiv b (mod \ n)$ and $ab \equiv 1 (mod \ n)$, it is very tempting to consider $a^2 \equiv 1 (mod \ n)$ [W.L.O.G]. Infact, reverse engineering we get that having this condition imposes both the conditions starting from either, given that $gcd(p,a)=gcd(p,b)=1$. We take cases, either n is odd or it is even. Case 1: n is odd, $gcd(n,2)=1$ thus $2^2 \equiv 1 (mod \ n)$ $\implies$ $3 \equiv 0 (mod \ n)$. We get $\boxed{\text n=1,3}$ which satisfy our conditions. Case 2: n is even, now we take subcase where $gcd(n,3)=1$ then $3^2-1 \equiv 8 \equiv 0 (mod \ n)$ $\implies$ $\boxed{\text n=2,4,8}$ Else, $3 \mid n$ and we take further cases $gcd(n,5)=1$ wherein we achieve, $5^2-1 \equiv 24 \equiv 0 (mod \ n)$ $\implies$ $\boxed{\text n=6,12,24.}$ Again we can assume $5|n$ which would lead to further cases for the prime being $7$ but manual checking gives no further solution. Claim: The maximum prime dividing n must either be 2 or 3. Proof: Consider $n=p_1^{z_1}p_2^{z_2}\ldots p_k^{z_k}$ wherein $k \in \mathbb{N}$. By FTA (Fundamental Theorem Of Arithmetic), we know that the form is finite and representable. Combined with euler's proof of existence of infinite primes. Let $P$ be the minimum prime not occuring in n greater than the maximal prime occuring in it. Thus we get $P \nmid n$ and $P>p_k$ assuming that $p_k>p_{k-1}>\cdots>p_1$. We consider the equation, $P^2 \equiv 1 (mod \ p_k)$ $\implies$ $P \equiv 1,(-1) (mod \ p_k)$. Notice that we can extend the argument to $P_k$ representing the $k-th$ smallest prime greater than the maximal prime dividing n such that $P_k \nmid n$. This would imply that every prime not dividing n must be in this sequence but more importantly, all primes $> p_k$ are of the form $P_k=p_k*t \pm 1$. Now, since the form of $n$ is finite it cannot just contain something like "all primes of a dirichlet form". We use the general statement of Dirichlet's Theorem which tells us that there are infinite primes in the arithmetic progression (let us consider a particular form) say, $a_n=p_k*(n-1)+2$ and obviously all such primes cannot be in n. The only other possibility is when atleast this form corresponds to $P_k=p_k*t \pm 1$ (we can extend to $a_n=p_k*(n-1)+3$ and so on) thus we get $2 \equiv \pm 1 (mod \ p_k)$ $\implies$ $3,1 \equiv 0 (mod \ p_k)$ $\implies$ $p_k=1,3$.Notice that, $p_k=1$ doesn't make any sense whereas $p_k=3$ is our original maximum through manual work. Infact, the reason for $p_k=2$ not occuring is because we need to also take into account that $p_k*t+2 \equiv 0 (mod \ p_k)$ which then forces $p_k=2$ and is our edge case. This completes the proof of claim. Now, we use this claim combined with our original cases thus limiting us to the fact that primes starting from 5 and so on can never divide n and thus the answers we found are the only ones. Q.E.D $\blacksquare$

Everything is trivial by CRT [INMOTC Karnataka insider joke] Consider the case where n is prime. Clearly as $a^2 \equiv 1$ mod $n$, $a \equiv 1, -1$ mod $n$ $\implies n = 2$ or $3$. Now by CRT, every such number has to be of the form $2^x3^y$. We look for the highest exponent of 2, which by trial and error is $2^3 = 8$. Similarly, the highest power of 3 is $3^1 = 3$. Therefore, the only possibilities are all factors of $2^3 \cdot 3^1 = 24$ (except $1$ as it is excluded). Clearly all these numbers work, so we are done. $\square$ Note: for higher powers of $2$, consider the case $a = 3$, and for higher powers of $3$, consider the case $a = 2$ for contradictions.

Why is the problem equivalent to $(A)$ $x^2 \equiv 1 \pmod n$ for all $\gcd(x,n) = 1$? We are given that $a \equiv b \pmod n \Leftrightarrow ab \equiv 1 \pmod n$ for $a$ and $b$ relatively prime to $n$. But we used $a \equiv b \pmod n \Rightarrow ab \equiv 1 \pmod n$ to get $(A)$?

Only if case: From the first $12$ values, get that $2,3,4,6,8$, and $12$ work. Then, if $n$ does not divide $2$, then $a=b=2$ results in $4 \equiv 1 \pmod n$, which is false. Similarly, if $n$ does not divide $3$, then $a=b=3$ results in $9 \equiv 1 \pmod n$, which is false. So $n$ has to divide $6$ Get that $24$ also works but $18$ does not. If $n \ge 25$, then if $n$ does not divide $5$, then $a=b=5$ results in $25 \equiv 1 \pmod n$, which is false. So $n$ has to divide $30$. Get that $30$ does not work and for $n \ge 60$, $a=7$ results in it not working So $n$ has to divide $420$, but then $a=11$ does not work, so it has to divide $420*11$, and then it repeats, so it does not work since $p_1*p_2*...*p_n > (p_{n+1})^2$ for large $n$ where $p_n$ is the nth prime. This can be proved by induction because it is true for $n=4$ and if $n$ works, then the LHS is multiplied by $p_{n+1}$, but the RHS is multiplied by $(\frac{p_{n+2}}{p_{n+1}})^2 \ge 2^2 = 4$, so the LHS will remain larger. So the only numbers that work are $\boxed{2,3,4,6,8,12,24}$ Testing, all of those satisfy the if case.

It is easy to see that the condition is equivalent to $a^2 \equiv 1 \pmod{n}$ for any $a$ with $gcd(a,n)=1$. Set $n=2^xk$ where $k$ is odd. Then $gcd(n,k+2)=1$ thus from the condition $$(k+2)^2\equiv 1\pmod{n} \Rightarrow 4 \equiv 1 \pmod{k} $$Hence $k\in\{1,3\}$ so $5^2\equiv 1 \pmod{n}$. Some case work gives us $n\in \{2,3,4,6,8,12,24 \}$ $$\mathbb{Q.E.D.}$$

I think I have a slightly different solution than those presented above. We claim the answer is $n = 2, 3, 4, 6, 8, 12, 24$. All can be checked to work. Now first, we will show that $n$ can only have $2$ or $3$ as prime factors. For the sake of contradiction, assume some prime $p_1 \ge 5$ divides $n$, and consider the prime factorization $n = p_1^{e_1} p_2^{e_2} \dots p_k^{e_k}$ where $p_i$ are primes and all $e_i$ are positive integers. Let $g$ be a primitive root of $p_1$. Then by Chinese Remainder Theorem, we can choose some residue $h \pmod{n}$ where $$h \equiv g \pmod{p_1^{e_1}}, h \equiv 1 \pmod{p_2^{e_2}}, \dots, h \equiv 1 \pmod{p_k^{e_k}}.$$Clearly the order of $h$ in $\pmod{n}$ is $p - 1 > 2$. Then we can choose $a = h, b = h^{p - 2}$ which must be distinct and multiply to $1 \pmod{n}$. Contradiction. Then the only prime factors of $n$ is $2$ or $3$. Now we can look at $a = 5, b = 5$, and we must have $25 \equiv 1 \pmod{n}$ which implies $n$ must be a factor of $24$ besides $1$. This implies the earlier mentioned solution set, and we are done.

Proving that $a^2 \equiv 1 \pmod{n}$ is enough for both way. Let us think about the case when $n = p$ where $p$ is a prime. For a prime $(a+1)(a-1) \equiv 0 \pmod{p}$, this means either $p$ divides $a+1$ or $a-1$ or it can be both. This we can observe as $a$ is the list of all numbers co prime to $n$, that $p = 2,3$ are the only primes satisfying this. Now, we can see that for any general $n$, if $n$ has factors other than powers of $2$ and $3$, there is a problem. Therefore, $n = 2^x.3^y$. To such a number the smallest coprime will be 5, so $5^2 -1 \equiv 0 \pmod{2^x.3^y}$ holds, This means that $2^x.3^y\leq 24$ By checking we get the solutions, 2,4,8,6,12,24

The only $n\ge 2$ that work are those satisfying $n\mid 24$. It is straightforward to check that these $n$ have the desired property; we now prove they are the only possible $n$. Suppose $n$ has the property that if $\gcd(a,n)=\gcd(b,n)=1$ and $a\equiv b \pmod{n}$, then $ab\equiv 1\pmod{n}$. This is equivalent to saying that all $a$ coprime to $n$ have order $2$ modulo $n$. By CRT, if $p \mid n$, then $a$ must have at most order $2$ modulo $p$. Note that if $p>3$, then $p$ has a primitive root with order greater than $2$, so no prime greater than $3$ can divide $n$. Also observe that by CRT again, if $p^k \mid \mid n$, then $a$ must have at most order $2$ modulo $p$. For an integer $r\ge 4$, we have $3^2 < 2^r$, so $3$ has an order greater than $2$ modulo $2^r$, and for an integer $s\ge 2$, we have $2^2 < 3^s$, so $2$ has an order greater than $2$ modulo $3^r$. Thus, $v_2(n)\le 3$ and $v_3(n)\le 1$, which implies $n\mid 24$. $\blacksquare$

just try to prove that $a^2 \equiv 1 \pmod{n}$ and $b^2 \equiv 1 \pmod{n}$ so $n\mid a^2-1$ and $n\mid b^2-1$ for all a,b $(a,n)=(b,n)=1$

We only consider $n$ prime power, as all other $n$ must be composed of prime powers that work. Now observe for odd prime powers greater than $4$, take $a = b = 2$, then $ab = 4$ which is not $1$ mod $n$. This leaves us to check $3$, which obviously works, and even prime powers. Observe $16$ fails since $16 \mid 5 \cdot 13 - 1$, so we check $8$. We check that $a^2 \equiv 1$ mod $8$ for all odd $8$, by injectivity of multiplication we can check the only if part, so $8$ works. By CRT, if two relatively prime things work, so do their product, and we know that the possible prime power divisors of $n$ are $2,3,4,8$, so the answer is just the divisors of $24$.

Note that this implies $a^2\equiv 1\pmod n$ for all $a$ coprime to $n$. Due to primitive roots, it follows that $n=2^k$ or $n=3\cdot 2^k$. It's easy to check such $n$ works when $k\le 3$ and doesn't work when $k>3$.

Note that $a \equiv b \implies a^2-1 \equiv 0 \pmod n.$ Therefore, for each prime power divisor of $n,$ $p_i^{e_i},$ $$a \equiv \pm 1 \pmod{p_i^{e_i}}$$if and only if $a$ is relatively prime to $n.$ Therefore, $p_i = 2, 3.$ Testing gives $2, 4, 8$ and $3,$ so the answers are just the divisors of $24.$

let a no. be good if for all a,b relatively prime to n, we have a = b(mod n) implies ab = 1 (mod n ). If some no. satisfies the inverse as well than call it perfect. Note that some no. is good only if all the factors of n are good. Claim 1 - If some prime p divides n (a perfect no.) than so do all the primes less than equal to p. for all p > 3 proof- you can use the fact that if p does not divide n that p^2 - 1 must be divisibe by n. note 5 is not a good no. so good no. are multilples of 2 and/or 3. using 5^2 - 1 is divisible by perfect no. we are done.