İ proved that $6|n$ but nothing appeared. Maybe dirichlet's theorem helps here?

Why is $6|n$ if $n=2$ is an obvious solution?

First prove that $2|n$ and note that $n=2$ is an obvious solution. We proceed as in this problem. Now suppose for some odd prime $p$, $p^k||n$. Then select $a$ such that $p||a-1$. Then by LTE, $\nu_p(a^n-1)=1+k$. But since $p^{2k}||2n^2|a^n-1$, we have $$2k\le 1+k$$$$\Rightarrow k=1$$. This implies that $n$ is squarefree. Similarly show that $2||n$. Hence $n=2p_1\cdots p_k$. This implies that $a^{2p_1\cdots p_k}\equiv 1\pmod {8p_1^2\cdots p_k^2}$. Suppose $p_1<p_2<\cdots p_n$ Note that $a^{(2p_1\cdots p_k, p_1-1)}\equiv 1\pmod {p_1}$. Now pick $a$ to be a primitive root modulo $p$. This means that $(2p_1\cdots p_k, p_1-1)=p_1-1$ but $p_1-1|2p_1\cdots p_k$ implies $p_1-1|2$ (since the other factors of $2p_1\cdots p_k$ are coprime to $p_1-1$). This just means that $p_1=3$. Continue this way to find that $p_2=7,p_3=43$ and then conclude that there cannot exist a $p_4$. Now verify that the solutions are $n=2$, $2\cdot7$, $2\cdot3\cdot7$, and $2\cdot3\cdot7\cdot43$.

rah4927 wrote: Now suppose for some odd prime $p$, $p|n$. Then select $a$ such that $p||a-1$. You have to prove that such $a$ exists. Because the condition is true for all $a$ coprime to $n$, not $p$. rah4927 wrote: Now pick $a$ to be a primitive root modulo $p$. Once again, you have to prove that, a primitive root modulo $p$ exists which is coprime to $n$ (since it is modulo $n$, not $p$). Though this case is sort of trivial for $p_1$.

ngv wrote: rah4927 wrote: Now suppose for some odd prime $p$, $p|n$. Then select $a$ such that $p||a-1$. You have to prove that such $a$ exists. Because the condition is true for all $a$ coprime to $n$, not $p$. rah4927 wrote: Now pick $a$ to be a primitive root modulo $p$. Once again, you have to prove that, a primitive root modulo $p$ exists which is coprime to $n$ (since it is modulo $n$, not $p$). Though this case is sort of trivial for $p_1$. Yeah, I sort of left some details out. Both of them can be shown by the Chinese Remainder Theorem.

rah4927 wrote: ngv wrote: rah4927 wrote: Now suppose for some odd prime $p$, $p|n$. Then select $a$ such that $p||a-1$. You have to prove that such $a$ exists. Because the condition is true for all $a$ coprime to $n$, not $p$. rah4927 wrote: Now pick $a$ to be a primitive root modulo $p$. Once again, you have to prove that, a primitive root modulo $p$ exists which is coprime to $n$ (since it is modulo $n$, not $p$). Though this case is sort of trivial for $p_1$. Yeah, I sort of left some details out. Both of them can be shown by the Chinese Remainder Theorem. Again, you need to show this. This is not trivial. You may be even wrong. For example, in the first case, CRT doesn't apply. $p|n$, so $p$ and $n$ are not coprime. The second case is not trivial either except for $p_1$, which is the smallest prime divisor of $n$. Because a primitive root of $p_1$ is less than $p_1$, so coprime to $n$. But you must guarantee the same for the latter primes. So, unless you can prove those, your solution is wrong. If you used CRT, you need to show that as well or I doubt you would get any marks in the original contest. In real contests, do not leave such important things out. Or they are counted as your assumptions, rather than being trivial stuff if they aren't actually trivial.

let $(a,n)=1$ then let $p$ does not divide $n$. Then $(a^{\phi(2n^2)}+p-1,n)=1$ then $ (a^{\phi(2n^2)}+p-1)^n\equiv p^n\equiv 1(mod$ $2n^2)$ by this way we can show that $p|n$ using LTE and orders. How to proceed for $p>43$ dont know.

ngv wrote: Again, you need to show this. This is not trivial. You may be even wrong. For example, in the first case, CRT doesn't apply. $p|n$, so $p$ and $n$ are not coprime. The second case is not trivial either except for $p_1$, which is the smallest prime divisor of $n$. Because a primitive root of $p_1$ is less than $p_1$, so coprime to $n$. But you must guarantee the same for the latter primes. So, unless you can prove those, your solution is wrong. If you used CRT, you need to show that as well or I doubt you would get any marks in the original contest. In real contests, do not leave such important things out. Or they are counted as your assumptions, rather than being trivial stuff if they aren't actually trivial. Okay, here are the details that I probably shouldn't have left out of my original solution. Suppose $n=p_1^{e_1}\cdots p_k^{e_k}$. Suppose $p=p_j$ for some $j$. Then pick $a$ such that the congruence system $$a-1\equiv p\pmod {p^2}$$$$a\equiv 1\pmod {p_i}\; \text{for i}\neq \text{j}$$is satisfied (a solution exists by CRT). Hence $p||(a-1)$ and $(a,n)=1$. As for the primitive root, pick any primitive root $g$ mod $p$. Now consider the congruence system $$a\equiv g\pmod p$$$$a\equiv 1\pmod {p_i}$$ This too has a solution by CRT. Please let me know if there are any other details missing.

We know that $(n,n-1)=1$ So put $a=n-1$ $2n^2 \mid a^n-1$ Take a $Pmin$ $ \mid 2n^2$ $P \mid(n-1)^n-1$ $$(n-1)^n\equiv 1\pmod p $$So $n \mid P-1$ So $p=2$ $n=1$

Abdollahpour wrote: We know that $(n,n-1)=1$ So put $a=n-1$ $2n^2 \mid a^n-1$ Take a $Pmin$ $ \mid 2n^2$ $P \mid(n-1)^n-1$ $$(n-1)^n\equiv 1\pmod p $$So $n \mid P-1$ So $p=2$ $n=1$ $is$ $it $ $true?$

Abdollahpour wrote: We know that $(n,n-1)=1$ So put $a=n-1$ $2n^2 \mid a^n-1$ Take a $Pmin$ $ \mid 2n^2$ $P \mid(n-1)^n-1$ $$(n-1)^n\equiv 1\pmod p $$So $n \mid P-1$ So $p=2$ $n=1$ wrong! It is easy to check that $n = 42$ is a solution.

Clearly $n=1$ doesn't work. Let $n > 1$. If $n$ has an odd prime divisor, call it $p$. Let $x = v_p(n)$. Since there exists a primitive root modulo $p^m$ for all $m \geq 1$, take a primitive root $g$ modulo $p^{2x}$ and choose $t$ such that $t\equiv g \pmod{p^{2x}}$ and $t$ is congruent to $1$ for all other primes dividing $n$. We can do that by the Chinese Remainder theorem. Now take $a = t$, we get $t^n \equiv g^n \equiv 1 \pmod{p^{2x}} \implies p^{2x - 1}(p - 1) \mid n$. From this, we deduce that $n$ cannot be odd. Thus, $x \geq 2x - 1 \implies x \leq 1 \implies x = 1$. Now, let $y = v_2(n)$. By LTE, we have $v_2(a^n - 1) = v_2(a - 1) + v_2(a + 1) + y - 1$. Choose $a$ such that $a \equiv 3 \pmod{8}$ and $a$ is coprime to $n$. (This is possible) Then, $v_2(a + 1) = 2$ and $v_2(a - 1) = 1$. So, $2y + 1 \leq y + 2 \implies y \leq 1 \implies y = 1$. So, $n$ is squarefree. If $n$ doesn't have any odd prime divisor, then $n=2$ and this works. Let $2 < p_1 < p_2 < \dots < p_k$ be the odd prime divisors of $n$. So $n = 2p_1p_2 \dots p_k$. From what we got earlier, we have $p_i - 1 \mid n$ for all $1 \leq i \leq k$. It is easy to see that all $n$ satisfying these conditions work. We have $p_1 - 1 \mid 2p_1p_2 \dots p_k \implies p_1 - 1 \mid 2p_1 \implies p_1 = 3$. Also, $p_2 - 1 \mid 6p_2 \implies p_2 - 1 \mid 6 \implies p_2 = 7$. Also, $p_3 - 1 \mid 42p_3 \implies p_3 - 1 \mid 42 \implies p_3 = 43$. Also, $p_4 - 1 \mid 1806p_4 \implies p_4 - 1 \mid 1806$ but there doesn't exist such prime with $p_4 > 43$. Thus, $k \leq 3$. If $k = 1$, then $n = 6$. If $k = 2$, then $n = 42$. And finally if $k = 3$, then $n = 1806$. So all solutions are $n = 2,6,42,1806$.