Uppalallalà!

OK, let's solve the first question ... For all odd $n$ we have $A_n$ non-empty If $n = 1$ then clearly $A_1 = \left\{ 1 \} \right.$. If $n > 1$ is an odd positive integer, we let $a = n - 1$. Then \begin{eqnarray*} a^n + 1 & \equiv & \left( n - 1 )^n + 1 \right.\\ & \equiv & ( - 1 )^n + 1\\ & \equiv & \left. 0 ( \mbox{ mod } n \right) \end{eqnarray*} Therefore for all odd positive integer $n$ we have $( n - 1 ) \in A_n$. For an even $n$ we have $A_n$ non-empty if and only if $n = 10$ Suppose that $n = 2 m$ for some positive integer $m$ and that \begin{eqnarray*} 2 m & | & a^{2 m} + 1 \end{eqnarray*} for some positive integer $1 \leq a \leq 2 m$. For all positive integer $k$ we have $k^2 + 1 \not \equiv 0 ( \mbox{ mod } 4 )$. Therefore $a^{2 m} + 1 \not \equiv 0 ( \mbox{ mod } 4 )$ and it follows that $m$ is odd (otherwise $4|2 m|a^{2 m} + 1$) For a positive integer $k$ any odd prime divisor of $k^2 + 1$ is $\equiv 1 ( \mbox{ mod } 4 )$. (Legendre) Therefore if $p$ is a prime such that $p|m$ then $p > 2$ and $p|m| \left( a^m )^2 + 1 \right.$ hence $p \equiv 1 ( \mbox{ mod} 4 )$. It follows that \begin{eqnarray*} 2^{2 \omega ( m )} = 4^{\omega ( m )} & | & \prod_{p^{\alpha} \| m} ( p - 1 ) \cdot p^{\alpha - 1} = \varphi ( m ) = \varphi ( 2 m )\\ 2^{2 \omega ( m )} & | & \varphi ( 2 m ) \end{eqnarray*} Now we have \begin{eqnarray*} a^{2 m} & \equiv & \left. - 1 ( \mbox{ mod } 2 m \right)\\ a^{4 m} & \equiv & 1 ( \mbox{ mod } 2 m ) \end{eqnarray*} This implies that $4 m| \varphi ( 2 m )$ or $\varphi ( 2 m ) |4m$ (since $( a, n ) = 1$ hence $a \in \mathbb{Z}_n^{\times}$). The case $4 m| \varphi ( 2 m )$ is clearly impossible since $4 m > 2 m > \varphi ( 2 m )$ for all positive integer $m.$ Therefore $2^{2 \omega ( m )} | \varphi ( 2 m ) | 4 m$, this implies that $2^{2 \omega ( m ) - 2} |m \Longrightarrow 2 \omega ( m ) - 2 = 0$ since $m$ is odd. Therefore $\omega ( m ) = 1$ and $n = 2 p^{\alpha}$ for some prime $p$ and a positive integer $\alpha$. Again this means that $\left. \varphi ( 2 p^{\alpha} \right) |4p^{\alpha}$ or that $\left. 4 p^{\alpha} | \varphi ( 2 p^{\alpha} \right)$. The later being impossible we must have \begin{eqnarray*} \left. \varphi ( 2 p^{\alpha} \right) & | & 4 p^{\alpha}\\ ( p - 1 ) \cdot p^{\alpha - 1} & | & 4 p^{\alpha}\\ p - 1 & | & 4 p \end{eqnarray*} Therefore $p = 5$. Hence $n = 10$. We check that $3 \in A_{10} .$ We have $A_n \neq \varnothing$ if and only if $n$ is odd or $n = 10$ I wonder, if there is a shorter solution...

I don't know where, but I think something went wrong in your proof {x}. Notice that $5^{26}\equiv 5^2\equiv -1\pmod{26}$ by Euler's Formula. I haven't tried very hard yet, but there probably is a shorter solution.

Damn, the wrong part is Quote: ... This implies that 4 m| $\varphi ( 2 m )$ or $\varphi ( 2 m )$ |4m ...

Let $n=2m$, $m$ such that if $p|m$ then $p=4k+1$. Then $\exists q$, $m|q^2+1$. Then $q^{2m}\equiv(-1)^m\equiv-1\pmod m$. Also $(m-k)^{2m}\equiv-1\pmod m$. Either $q$ or $m-k$ is odd. Consider $q$ odd. Then $2m|q^{2m}+1$. Obviously, $|A_n|$ for such $n$ is even (if $q\in A_n$ then $n-q\in A_n$).

Can someone please solve the last question?

Let $\phi (2m)|4m$, were m is odd. If $m=p_{1}^{k_{1}}p_{2}^{k_{2}}...p_{s}^{k_{s}}$ we have $ord_{2}(\phi (2m))=\sum_{i}ord_{2}(p_{i}-1)$. Therefore $s\le 2$. If $m=p^{k}$ then $p=3$ or $p=5$. It give $2m=2*3^{k}\ or \ 2m=2*5^{k}$. If $m=p_{1}^{k_{1}}p_{2}^{k_{2}},p_{1}<p_{2}$ then $p_{1}=3,p_{2}=7$. Therefore $2m=2*3^{k_{1}}*7^{k_{2}}$.

Fun problem. I don't think my solution is very tricky, maybe there is a shorter way. For part a, we make the observation that we can always choose $a = n-1$ for when $n$ is odd. The only exception is 1, but that clearly also works. Now we consider $n$ being even. We have two cases. Assume $4|n$: This means that $n = 4k$ so that $4k|a^{4k}+1$ Since we know that $gcd(a,n) = 1$, it is clear that $a^{4k}\equiv 1 \pmod 4$ Thus, we have a contradiction. So we know that even $n$ are of the form $2k$. Where $k$ is an odd integer. Now notice that $a^{n}\equiv-1 \pmod n$ with $n$ being even. So we have that $(a^{\frac{n}{2}})^{2}\equiv-1 \pmod n$ Thus we know that $-1$ is a square in mod $n$. We conclude that the only prime divisors $p$ of $k$ must have $p \equiv 1 \pmod 4$. I claim that that is indeed all we need. Notice that $2k \equiv 2 \pmod 4$, since $k$ is odd. Thus if we have that $a^{2}\equiv-1 \pmod n$, then $a^{2k}\equiv-1 \pmod n$. So we would have at least those two solutions. But of course we could find such an $a$. It is guaranteed by exactly the condition that the only prime divisors of $k$ are congruent to 1 mod 4. So we are done. The answer is all odd $n$ or even $n$ of the form $2k$ where the only prime divisors of $k$ are 1 mod 4. Now onto part b. I think the arguement follows fairly naturally after you decide that they asked only whether or not the number of solutions is even, not to actually count the number. The answer seems to be for all the $n$ of the second type listed above except 2. The ones that are even and have at least one $a$ that work. It is easy to prove it for those particular $n$. Since $n$ is even we have $a^{n}\equiv (-a)^{n}\pmod n$ So each solution must have another corresponding solution. The only way this could fail is if $a \equiv-a \pmod n$. But since we have that $gcd(a,n) = 1$ we know this is only possible when $n=2$ which is indeed the only exception. Now we consider the odd $n$. We have to count some solutions by using CRT. We first prime factor $n$ and then consider one of the prime powers at a time. Find the number of solutions in each of those mods and multiply. Clearly, we are done if we find that there are an odd number of solutions in each mod on its own. Now we consider the equation we are solving $a^{n}\equiv-1 \pmod{p^{t}}$ Where we have that $p^{t}|n$ and that $n$ is odd. We have also that $a^{2n}\equiv 1 \pmod{p^{t}}$. Thus, we know that $ord(a)|2n$ but it doesn't divide $n$. In fact that condition is sufficient since in mod $p^{t}$ where $p$ is odd, $\pm 1$ are the only square roots of 1 (that fact follows directly from factoring or from hensel's lemma). In other words we are looking for all the elements of mod $p^{t}$ with certain orders and we are counting their parity. We take advantage of the fact that the multiplicative group of mod $p^{t}$ has a generator to conclude that the number of elements with order $x$ is $\phi(x)$. But we know that $\phi(x)$ is always even except when $x = 1,2$. We since the order of $a$ divides $2n$ and not $n$, it is clear it is of the form $2k$ where $k$ is odd. Clearly the only odd number of solutions we are going to get is when $k=1$. But that actually works in this case. So we are done! To do part c, we need only be a little bit more careful about the arguement we just used for part b. Based on part b we need only consider even $n$ that work. We start counting solutions again. So we have that the number of solutions to $a^{n}\equiv-1 \pmod n$ must be 130. The way to find these solutions is to first consider each prime power divisor separately again and then multiply the number together using CRT. Remember that in this case $n$ has exactly one factor of 2. In mod $p^{t}$ the number of solutions is exactly the same order trick again. However, in this case, things with order 2 do not work anymore. In other words, there is an even number of solutions in each prime power mod. Thus we can actually only have 1 prime power, since 4 does not divide 130. This simplifies the problem a lot and leaves us with solving the problem of finding the number of solutions to $a^{2p^{t}}\equiv-1 \pmod{p^{t}}$. Doing a little bit of simplifying with euler we get that $a^{2p^{t-1}}\equiv-1 \pmod{p^{t}}$. Or in other words we have $ord(a)|4p^{t-1}$ but not $2p^{t-1}$. Which is also a sufficient condition again. Therefore we conclude $ord(a) = 4, 4p, 4p^{2}, \cdots, 4p^{t-1}$. Keep in mind that these are legitimate orders since $p \equiv 1 \pmod 4$. How many solutions do we have total? Based on what we concluded earlier it simply: \[\phi(4)+\phi(4p)+\cdots \phi(4p^{t-1}) = 2(1+(p-1)+(p^{2}-p)+\cdots (p^{t-1}-p^{t-2})) = 2p^{t-1}\neq 130\] Yay!

i think there are two solutions of $a^{2}=-1(mod p^{k})$ for $p=1(mod4)$ this can be made by induction. (or i think i have made)

I solved it last summer, by using primitive root.

This problem solved at Sierpinski "250 problems of elementary number theory" №22

Beautiful problem that doesn't get the love. We will ignore $n=1,2$, as these are stupid useless numbers that make life challenging. They only work for part (a). We claim the answer to part (a) is the following: Let $\mathcal P_{\geq 3}$ be the set of odd primes, and $\mathcal P_{1\pmod 4}$ be the set of primes 1 modulo 4. Then, $n$ has all prime factors in $\mathcal P_{\geq 3}$ or $\{2\}\cup\mathcal P_{1\pmod 4}$. Note that if $4\mid n$, then clearly \[\{a^n+1\}\subseteq\{a^2+1\}\subseteq\{1,2\pmod 4\}\]so thus $4\nmid n$. Now, if $n$ is odd, taking $a=n-1$ gives \[a^n+1\equiv (-1)^n+1\equiv 0\pmod n\]Now, if $n$ is even, suppose $p\mid n$. Then, $a^2+1\equiv 0\pmod p$ has a solution, so $p\equiv 1\pmod 4$. For the converse, note that $p=x^2+y^2$ for any $p\equiv 1\pmod 4$, and thus we can note $|x+yi|=\sqrt p$. Thus, \[p^k=|(x+yi)^k|^2\]and thus we can write all powers of $p$ as the sum of two squares. In particular, we can find a solution to $p\equiv -1\pmod{p^k}$, so the solution to (a) is indeed as mentioned. For part b, we note that if $n$ is even (and greater than 2), then $a$ and $n-a$ both work (clearly $a=n,\frac n2$ fails). If $n$ is odd, then clearly note that there are actually $\gcd(n,p-1)$ solutions to $x^n+1\equiv 0\pmod p$ - let $g$ be a primitive root modulo $p$, and note this implies that the number of solutions is the number of $1\leq k\leq p-1$ such that \[nk\equiv 0\pmod{p-1}\]which has $\gcd(n,p-1)$ solutions. As $n$ is odd, this is odd. Now, by Hensel's Lemma, for a prime power $p^k\mid n$, the number of solutions to \[x^n\equiv -1\pmod{p^k}\]is $p^{k-1}\gcd(n,p-1)$, so applying the Chinese Remainder Theorem, we get the desired result. For part c, the answer is "no". If $p_1\neq p_2\in\mathcal P_{\geq 3}$ divided $n$, by our above discussion, there are $4\mid p_1^{k_1-1}\gcd(n,p_1-1)p_2^{k_2-1}\gcd(n,p_2-1)$ solutions, a contradiction. Thus, $n=2p^k$, impossible.

Solution from Twitch Solves ISL: Part (a): The answer is odd $n$ and even $n$ with $\nu_2(n) \le 1$ and only $1 \bmod 4$ prime factors. For odd $n$, let $a = n-1$ for a construction. For even $n$, the right-hand side is a sum of two squares, one of which is odd. So $\nu_2(n) \le 1$ and the $1 \bmod 4$ condition are both needed. Conversely, we can choose $n$ to be a square root of $-1$ modulo each prime power dividing $n$; this works. Part (b): The answer is all even numbers in (a) other than $n=2$. As for evenness: When $n$ is even, pairing $a$ and $-a$ implies $|A_n|$ even, except $n=2$ (the only time $n \mid (n/2)^n+1$). When $n$ is odd, the number of solutions to $a^n \equiv -1 \pmod{p^e}$ for odd prime power $p^e$ is odd: $a \equiv -1$ is a solution, $a \equiv 1$ is not, and any other solutions come in pairs $\{a,1/a\}$. Part (c): No. If such $n$ existed, by (b) it is even. If $n$ has more than one distinct odd prime factor, then $|A_n|$ is divisible by four, by Chinese remainder theorem. For $n = 2p^e$, \[ a^{2p^e} \equiv -1 \pmod{p^e} \]We have a primitive root, of order $(p-1) \cdot p^{e-1}$. So there are $2p^{e-1}$ solutions. Neither case coincides with $130$, end proof.