Factorial: n!|a^n+1

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

160 posts

#1 h Apr 24, 2006, 10:55 AM • 17 Y

Y by Davi-8191, tenplusten, Mathuzb, nguyendangkhoa17112003, rashah76, itslumi, Adventure10, megarnie, TheHawk, yshk, Mango247, Sedro, cubres, and 4 other users

Find all positive integers $n$ such that there exists a unique integer $a$ such that $0\leq a < n!$ with the following property:
$n!\mid a^n + 1$

Proposed by Carlos Caicedo, Colombia

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

jin

383 posts

jin

#2 h Apr 25, 2006, 2:39 AM • 5 Y

Y by Adventure10, TheHawk, yshk, Mango247, and 1 other user

If $n$ is even, $a^n+1=x^2+1,(x=a^{\frac{n}{2}})$
So 3 doesn't divide $a^n+1$ and we see 3 doesn't divide $n!$
So $n=2$ .
But what if $n$ is odd,

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Megus

1198 posts

Megus

#3 h Apr 25, 2006, 6:58 PM • 4 Y

Y by Adventure10, TheHawk, yshk, Mango247

We can use well-known (actually I never proved it with $a+1$ but rather $a-1$ but in this case I bet result is still valid and proof doesn't change much [induction])

if $p^b || a+1$ then $p^c || n$ is equivalent to $p^{b+c}||a^n+1$ . Using that $v_p (n!)= \sum_{i=1} ^{\infty} [\frac{n}{p^i} ]$ we can compare $v_p(a^n+1)$ and $v_p(n!)$ and quickly bring whole problem to checking manually some small $n$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ZetaX

7579 posts

ZetaX

#4 h Apr 25, 2006, 7:05 PM • 4 Y

Y by Adventure10, TheHawk, sabkx, Mango247

No you cant since there are $\infty$ many $n$ with that property

Or how would you do it¿

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Megus

1198 posts

Megus

#5 h Apr 25, 2006, 7:11 PM • 3 Y

Y by Adventure10, TheHawk, Mango247

I would fix $n$ and assume that there exist such an $a$ , then use above (from which we get bound on $n$ ) - is there really infinite number of solutions ?

(can you show some infinite family of solutions)

Edit: I've seen my mistake - I thought $0 \leq a < n$

This post has been edited 3 times. Last edited by Megus, Apr 25, 2006, 7:28 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ZetaX

7579 posts

ZetaX

#6 h Apr 25, 2006, 7:18 PM • 3 Y

Y by Adventure10, TheHawk, Mango247

Exactly the primes work

But I will not post a proof that they work since this spoils half of the problem.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

rem

1434 posts

rem

#7 h Apr 25, 2006, 8:00 PM • 3 Y

Y by Adventure10, TheHawk, Mango247

Nima Ahmadi Pour wrote:

Find all $n$ such that there exists a unique integer $a$ such that $0\leq a<n!$ with the following property:
$n!|a^n+1$

If $n!$ divides $a^n+1$ then $gcd(n,a) = 1$ . But $a < n$ . Hence $a = 0$ or $1$ . Then $n!$ can be $1$ or $2$ , so $n$ is $1$ or $2$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ZetaX

7579 posts

ZetaX

#8 h Apr 25, 2006, 8:14 PM • 3 Y

Y by Adventure10, TheHawk, Mango247

Surely not, just try $n=3,5,7,...$

I think you missinterpreted some places of $!$ 's.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

rem

1434 posts

rem

#9 h Apr 25, 2006, 8:17 PM • 3 Y

Y by Adventure10, TheHawk, Mango247

Sorry

it's $a<n!$
I 'll try to come up with a solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

cefer

293 posts

cefer

#10 h Apr 27, 2006, 10:51 AM • 11 Y

Y by Illuzion, Polynom_Efendi, Feridimo, Adventure10, aidan0626, TheHawk, yshk, sabkx, Mango247, and 2 other users

Check that for $n=2,3$ there is unique $a$ satisfying problem. Now assume $n \geq 4$ .
- If $n$ is even then $4|n!$ . Hence $4|a^n+1$ and we get a contradiction.

- If $n$ is odd composite then there are at least two such $a$ 's: Obviously for $a=n!-1$ we have $n!|a^n+1$ . Lets prove that if $a=(n-1)!-1$ then $n!|a^n+1$ . Note that
$a^n+1=((n-1)!-1)^n+1=((n-1)!)^2A+(n-1)!n-1+1=((n-1)!)^2A+n!$
Because $n$ is composite $n!|((n-1)!)^2$ and so $n!|a^n+1$ . Hence there are at least two such $a$ 's.

- If $n$ is prime then there is unique such $a$ : Let $n!=p!=r_1^{a_1}r_2^{a_2}....r_k^{a_k}$ be the prime factorization of $n!$ and let $(r,b)=(r_i,a_i)$ for some $i$ so that $r^b|a^p+1$ . Then $r^b|a^{2p}-1$ and from Euler's theorem we also have $r^b|a^{r^{b-1}(r-1)}-1$ . So $r^b|a^d-1$ where $d=\gcd(2p,r^{b-1}(r-1))|2$ . If $d=1$ then $a^p+1\equiv 2 \mod r^b$ which is obviously a contradiction. So $d=2$ and $r^b|a^2-1=(a-1)(a+1)$ . If $r$ is odd then then $a\equiv 1 \mod r^b$ or $a\equiv -1 \mod r^b$ . As above we must have $a \equiv -1 \mod r^b$ . If $r=2$ then taking $a=2k+1$ gives $2^{b-2}|k(k+1)$ . If $k\equiv 0 \mod 2^{b-2}$ then $a^p+1=(2k+1)^p+1\equiv 2 \mod 2^{b-1}$ . Since $b \geq 3$ this is a contradiction. So $k\equiv -1 \mod 2^{b-2}$ and $a\equiv -1 \mod 2^{b-1}$ . If $a\equiv 2^{b-1}-1 \mod 2^b$ then
$a^p+1 \equiv (2^{b-1}-1)^p+1 \equiv 2^{b-1} \mod 2^b$
This gives $a\equiv -1 \mod 2^b$ . Thus we proved that $a\equiv -1 \mod r_i^{a_i}$ for all $i$ . From the Chinese remainder theorem this system of equations has unique solution in $[1, r_1^{a_1}r_2^{a_2}....r_k^{a_k})=[1, p!)$ . Hence when $n$ is prime there is unique such $a$ .

This post has been edited 1 time. Last edited by cefer, May 22, 2014, 12:32 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

The QuattoMaster 6000

1184 posts

The QuattoMaster 6000

#11 h Nov 30, 2008, 6:24 PM • 4 Y

Y by TheHawk, Adventure10, Mango247, and 1 other user

I have the same as cefer for evens and primes, but my proof for odd composite is a little different.
Solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

bodan

267 posts

bodan

#12 h Jun 26, 2009, 1:32 PM • 5 Y

Y by pavel kozlov, TheHawk, Adventure10, Mango247, and 1 other user

Note that $n = 1, 2, 3$ are solutions. Suppose that $n \geq 4$ is a solution, and let $a$ be the unique integer. $a$ and $n!$ are relatively prime, since $(a, n!) \leq (a^n, n!) \leq (a^n, a^n + 1) = 1$ .

I. The equation $x^n \equiv_{n!} 1$ does not have a solution in $2 \leq x \leq n!$ .
Proof. Suppose the contrary, and let $2 \leq x \leq n!$ be a solution to that equation. Then $(ax)^n \equiv a^n x^n \equiv - 1 \pmod {n!},$ hence $ax \equiv_{n!} a$ hence $x \equiv_{n!} 1,$ contradiction.

II. $n$ is prime.
Proof. Suppose the contrary, and let $q$ be the least prime divisor of $n,$ so that $2q \leq n.$ Then $q \,|\, \tfrac{n!}{q},$ and $x = \tfrac{n!}{q} + 1$ satisfies $x^n - 1 = \tfrac{n!}{p} (1 + x + \cdots + x^{n - 1})$ and also $1 + x + \cdots + x^{n - 1} \equiv_p 1 + 1 + \cdots + 1 \equiv_p 0,$ hence $n!$ divides $x^n - 1,$ contradiction.

III. All primes are solutions.
Proof Let $p$ be a prime. Then $a = p! - 1$ is a solution to $p! \,|\, a^p + 1.$ Suppose that $b$ is another solution, then (because both are relatively prime to $p!,$ ) $b^{ - 1}a \bmod p!$ is a solution to $x^p \equiv_{p!} 1,$ then $(x, p!) = 1$ so if $\delta$ is the order of $x$ modulo $p!$ it must be $\delta \, |\, p$ and $\delta \,|\, \phi(p!),$ and since $(p, \phi(p!)) = 1,$ $\delta = 1,$ so $x = 1.$ Hence $b^{ - 1} a = 1$ so $a = b$ and we have that $a$ is indeed unique.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Zhero

2043 posts

Zhero

#13 h Mar 11, 2010, 2:26 AM • 6 Y

Y by TheHawk, Adventure10, Mango247, and 3 other users

Is this right?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

sjaelee

485 posts

sjaelee

#14 h Oct 10, 2012, 1:58 AM • 5 Y

Y by B.J.W.T, yayitsme, TheHawk, Adventure10, Mango247

Solution with help from dinoboy and yugrey

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

JuanOrtiz

366 posts

JuanOrtiz

#15 h Apr 16, 2014, 4:43 PM • 2 Y

Y by TheHawk, Adventure10

Easy problem. This is my solution

ONE MUST NOT FORGET: Also note that if $n=1$ , the only possible $a$ is $a=0$ since $0 \le 0 \textless 1$ and it works, so $n=1$ works.

Zhero wrote:

Note that $n \neq 1$ , since we cannot find an integer between 0 and 1!.

That is wrong since $n=1$ is possible.

So we are done and the answer is answer

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Tyx2019

22 posts

Tyx2019

#57 h Oct 1, 2023, 6:58 AM

Y by

The answers are $n=1,n=2$ and $n$ prime.

First settle trivial case of $n$ even. If $n$ is even, -1 must be a quadratic residue mod all primes $<n$ . So then if $n\geq 3$ 2 is a quadratic residue mod 3 which is wrong.

Now we have $n$ is odd. If $n$ is not prime and not 1, then it can be split into $pr$ where $p$ is prime and $r\geq 2$ . Hence we have $2p\le n$ , so $v_p(n!)\geq 2$ . Let $k=v_p(n!)$ . Now since such a solution is unique, and there is at least one solution( $a=p!-1$ ), then if there is more than 1 solution to $a^n\equiv -1$ mod $p^k$ in the range $[0,p^k-1]$ then there are more than 2 solutions(by CRT).

Let us choose a primitive root $g$ of $p^k$ . Then $g^{\frac{p^k-p^{k-1}}{2}}\equiv -1 \mod{p}$ , and we only need to show that $xn \equiv \frac{p^k-p^{k-1}}{2} \mod{p^k-p^{k-1}}$ has more than 1 solution, which is obvious.

Now if $n$ is prime, it works. Firstly if there is only one solution for each $p$ for $xn \equiv \frac{p^k-p^{k-1}}{2} \mod{p^k-p^{k-1}}$ if $k=v_p(n)$ we are done. This is because by CRT there will only be one solution mod $n!$ . So, this is obvious for primes $<n$ since $n$ is coprime to $p^k-p^{k-1}$ (coprime to $p$ and $p-1$ ). Clearly for $p=n$ , $n$ is coprime with $n-1$ so we are done, since $v_n(n!)=1$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

KI_HG

157 posts

KI_HG

#58 h Nov 12, 2023, 11:55 PM

Y by

One can use Hensel to generate another solution.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

OronSH

1728 posts

OronSH

#59 h Dec 7, 2023, 3:04 PM • 1 Y

Y by mathmax12

The answer is all primes and $1$ which is trivial. For evens $>2$ we have $n! \equiv 0 \pmod 4,$ so $a^n \equiv 3 \pmod 4$ but is a square, impossible. We check $n=2$ works.

If $n$ is odd and is a prime $p$ then the order of $a \pmod p$ must divide $2p$ but not $p$ so it must be either $2$ or $2p.$ But it must also divide $\varphi(p!)$ so it is not $2p.$ Thus $a^2 \equiv 1 \pmod p$ so $a^p \equiv a \pmod p$ so $a \equiv -1 \pmod p$ and $a=p!-1$ is the only solution which works.

If $n$ is odd and composite, we take $a=(n-1)!-1$ and since $n \mid (n-1)!$ we have $n! \mid (n-1)!^2$ so when we expand all terms of $a^n$ using the binomial formula all terms must be divisible by $n!$ except for the last two, but the second to last term is $(n-1)! \cdot n = n!$ so it is also divisible by $n!$ so $a^n \equiv -1 \pmod{n!}$ and $n! \mid a^n+1.$ However we can also just take $a=n!-1$ so these don't work and we are done.

This post has been edited 2 times. Last edited by OronSH, Dec 7, 2023, 3:08 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

AlanLG

241 posts

AlanLG

#60 h Feb 3, 2024, 6:25 PM

Y by

$\textcolor{blue}{\text{Claim } n \hspace{0.2cm}\text{even doesn´t work}}$
We would have for some $p\mid n!$ prime $p\mid a^n+1$ so by Fermat Christmas Theorem $p=2$ or $p\equiv 1\pmod 4$

$\textcolor{blue}{\text{Claim } n \hspace{0.2cm}\text{odd and composite doesn´t work}}$
As $n$ odd $n\mid (n!-1)^n-1$ so $a=n!-1$ works
One way to found a contradiction

Another way
$\textcolor{blue}{\text{Claim } p \hspace{0.2cm}\text{prime work}}$
Let $q\mid p! \hspace{0.1cm}$ prime, so $a^{2p}\equiv 1\pmod q$ and $a^{q-1}\equiv 1\pmod q$ so $\operatorname{Ord}_q(a)\mid 2\gcd\left(p,\frac{q-1}{2}\right)$ so $\operatorname{Ord}_q(a)=2$ thus $q\mid a+1$ , then
$\nu_q\left(a^p+1\right)=\nu_q(a+1)+\nu_q(p)=\nu_q(a+1)$ So $p!\mid a+1$ then $a=p!-1$ is the unique solution here

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

joshualiu315

2513 posts

joshualiu315

#61 h Feb 12, 2024, 8:20 PM

Y by

The answer are the $\boxed{\text{primes}}$ . If $n$ is even and greater than $2$ , we have

$a^n \equiv -1 \pmod{n!} \iff a^n \equiv -1 \pmod{4},$
which is impossible.

Manually check that $n=2$ is valid, so assume $n$ is odd henceforth.

If $n$ is prime, we have

$a^n \equiv -1 \pmod{n!}$ $\implies a^{2n} \equiv 1 \pmod{n!}.$
Hence, the order of $a$ modulo $n!$ is divisible by $2n$ but not $n$ . This means it is either $2$ or $2n$ . Consider a prime $p \mid n!$ .

We have

$a^{p-1} \equiv 1 \pmod{p},$
so the order of $a$ modulo $n!$ is $\gcd(p-1, 2n) = 2$ . This means that

$a^n \equiv a \equiv -1 \pmod{p!},$
fixing $a=p!-1$ .

If $n$ is odd and composite, $a=n!-1$ still is valid, but we claim $(n-1)!-1$ will also be valid, violating the uniqueness of $a$ . Note that

$\nu_{p}(((n-1)!-1)^n+1) = \nu_{p}((n-1)!) + \nu_{p}(n) = \nu_p(n!).$
We are done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

shendrew7

793 posts

shendrew7

#62 h Mar 3, 2024, 2:22 AM

Y by

We claim the answer is $\boxed{\text{all primes}}$ .

For all primes $n=p$ , we claim the desired unique integer is $p!-1$ , which clearly works. To prove this, take an arbitrary prime $q<p$ , and note we require
$a^p \equiv -1 \pmod q \implies \operatorname{ord}_qa \mid 2p, q-1 \implies \operatorname{ord}_qa = 2 \implies q \mid a+1.$ We conclude using LTE to get
$v_q(p!) \leq v_q(a^p+1) = v_q(a+1) \implies p! \mid a+1 \implies a=p!-1.$
For all evens other than 2, notice that if $m$ works, $n!-m$ also works (and clearly $\tfrac{n!}{2}$ always fails), giving us two distinct values. For all odds, we simply take $n!-1$ and $(n-1)!-1$ . $\blacksquare$

This post has been edited 1 time. Last edited by shendrew7, Mar 3, 2024, 2:23 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Marius_Avion_De_Vanatoare

54 posts

Marius_Avion_De_Vanatoare

#63 h Jun 11, 2024, 5:36 AM

Y by

Nice training problem, the answer are all prime numbers.
First note that if $n$ is even, for a solution $a$ , $n!-a$ is also a solution, thus $a=\frac{n!}{2}$ , which only works for $n=2$ .
For odd $n$ the only solution should be $n!-1$ , for composite $n$ , however take $\frac{n!}{p}-1$ , for some prime $p$ dividing $n$ , and see that for example by $LTE$ , $v_p(a^n+1)=v_p(a+1)+v_p(n) \ge v_p(n!)-1+1=v_p(n!)$ , or just factor out and see that the second paranthesis is also divisible by $p$ .
Now for prime $n$ , any prime dividing $a^n+1$ divides $a^{2n}-1$ , thus it's order divides $2n$ , but as it also divides $p-1$ , for primes $p\le n$ we get that it divides $2$ , meaning together with $p \mid a^n+1$ , that $p \mid a+1$ for any prime $p\le n$ , and using $LTE$ or factorization again it is easy to see that $\frac{a^n+1}{a+1}$ does not contribute with any prime power, thus we get $n! \mid a+1$ , which is the desired conclusion.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

SenorSloth

37 posts

SenorSloth

#64 h Jun 18, 2024, 2:18 AM

Y by

We claim that the answer is all prime $n$ , with $a=n!-1$ the unique value of $a$ in those cases.

First, we prove that this works. For $n=2$ , $a=1$ is the unique integer that works. For larger $n$ , assume that $n!=p_1^{e_1}\cdot p_2^{e_2}\dots p_k^{e_k}\cdot n$ , where $p_1$ through $p_k$ are the primes less than $n$ . For any prime $p<n$ , we will show that $p^k\mid a^n+1$ implies that $a\equiv -1 \pmod{p^k}$ . The order of $a\pmod{{p_i}^{e_i}}$ must divide $\gcd((p-1)p^{k-1},2n)$ , which equals $2$ since $n$ is a prime greater than $p$ . The order can't be $1$ , so it must be $2$ , which then implies that $a\equiv -1 \pmod{{p_i}^{e_i}}$ . Then for the prime $n$ , since $a^n\equiv a\pmod{n}$ by FLT, for $n\mid a^n+1$ we require $a\equiv -1 \pmod{n}$ . Then by CRT over all of the prime powers dividing $n!$ , there is only one solution.

Now we must prove that other numbers do not work. Even values of $n>2$ fail since $4\mid n!$ but $a^n+1$ can only be $1$ or $2\pmod{4}$ . For odd composite $n$ , consider a prime $p$ dividing $n$ , and let $k$ be the maximum value such that $p^k\mid n!$ . If we let $a\equiv -1\pmod{p^{k-1}}$ , we can apply LTE to get that $\nu_p(a^n+1)=\nu_p(a+1)+\nu_p(n)\geq k-1 +\nu_p(n)$ . Since $p\mid n$ , $\nu_p(n)\geq 1$ , so $\nu_p(a^n+1)\geq k$ and $p^k\mid a^n+1$ . Thus there are $p$ different values $\pmod{p^k}$ that are $-1\pmod{p^{k-1}}$ , each of which could be used when applying CRT over all of the prime powers. This tells us that the number of solutions will be a multiple of $p$ , but this can clearly never be $1$ . Thus prime $n$ are the only solutions, as desired.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

AshAuktober

981 posts

AshAuktober

#65 h Aug 17, 2024, 5:48 AM

Y by

The solution set is $\boxed{n = 1 \text{ and } n \text{ prime.}}$
Lemma 1: $n \in \{1, 2\}$ work trivially.

Lemma 2: If $n$ works and is even, $n = 2$ .
Proof: Assume otherwise, letting $n = 2k$ . Then $3 \mid n! \mid (a^k)^2 + 1$ , impossible by Fermat's Christmas Theorem.

Lemma 3: All odd composite numbers don't work.
Proof: Same as anantmudgal09, so copied from there:
Let $n$ be an odd composite number. Let $r$ be a prime factor of $n$ . We show that there is a number $a$ which works other than $n!-1$ which obviously does. Now, ofc we get by LTE; $v_r(a^n+1)=v_r(a+1)+v_r(n) \ge v_r(n!)$ and so we set $a \equiv -1 ( \bmod r^{v_r((n-1)!)})$ for all $r \mid n$ . Otherwise, we set $a \equiv -1 (\bmod r^{v_r(n!)})$ for all $r$ prime divisors of $n!$ but not $n$ . This clearly gives a working $a$ and infact by CRT, generates at least $n$ such $a$ 's in the range $[0,n!)$ and we conclude that more than one such number exist. This proves that odd composites are failed by the proposition.

Lemma 4: All odd primes work.
Proof: Attached below.
Due to the above, the solution set is confirmed. $\square$

Attachments:

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

kotmhn

57 posts

kotmhn

#67 h Sep 12, 2024, 6:09 PM

Y by

\begin{answer}
Only primes and 1 work as the value of $n$
\end{answer}
\begin{proof}
\textbf{Prime $n$ gives unique solution}

let $p! = p_1^{\alpha_1} \dots p_k^{\alpha_k}$
so we need solution to $a^p \equiv -1 \pmod{p_i^{\alpha_i}}$
Clearly we have that $\gcd(p,p_i^{\alpha_i})=1$ then clearly $a^p$ is a bijection and we are done, as it gives out unique values for each
$p_i^{\alpha_i}$ and then we apply CRT to finish.

\textbf{Composite $n$ do not work}

let $n! =p^{\nu_p(n!) }\cdot k$ where p is chosen such that $p \mid n \Rightarrow n=p\cdot t$
\begin{claim}
if a solution to $a^n \equiv -1 \pmod{p^{\nu_p(n!)}}$ multiple solutions exist.
\end{claim}
\begin{proof}
So we need $a^{pt} \equiv b^{pt} \equiv -1 \pmod{p^{\nu_p(n!) }}$ to have solutions in distinct $a,b$ .
clearly $a,b$ have to be co prime to $p_i$ and getting $a^p \equiv b^p \pmod{p^{\nu_p(n!) }}$ works as i can raise both to $t$ therefore we need
\begin{center}
$\left(\frac{a}{b} \right)^{p} \equiv 1 \pmod{p^{\nu_p(n!)}}$
\end{center}
then clearly taking primitive roots we seen that this has multiple solutions.
\end{proof}
this clearly shows that composite $n$ do not work.
\end{proof}

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

EpicBird08

1743 posts

EpicBird08

#68 h Oct 13, 2024, 10:01 PM

Y by

The answer is all prime $n.$ (And $1$ as well. bruhhhhh)

First, we verify that the only even $n$ that works is $n = 2.$ For $n = 2,$ only $a = 1$ works, while for even $n > 2,$ if $a$ works, then so does $n! - a,$ and since $\frac{n!}{2}$ clearly doesn't work, we get an even number of solutions. Henceforth assume that $n$ is odd.

Verification that odd primes $p$ work: We want $a^p \equiv -1 \pmod{p!},$ or $(-a)^p \equiv 1 \pmod{p!}.$ We want to show that there is exactly one value of $a$ which satisfies this, namely $a = n!-1.$ This is equivalent to showing that the order of any number modulo $p!$ cannot be $p.$ In fact, $p \nmid \phi(p!)$ because $\phi(p!) = p! \cdot \prod_{q < p, q \text{ is prime}} \left(1 - \frac{1}{q}\right)$ has all of its prime factors less than $p.$ This means that if $(-a)^p \equiv 1 \pmod{p!},$ then $-a \equiv 1 \pmod{p!},$ giving exactly one solution, as required.

Proof that odd composites $n$ don't work: Once again we would like to solve $(-a)^n \equiv 1 \pmod{n!}.$ For simplicity let $b = n!-a,$ so that we want $b^n \equiv 1 \pmod{n!}.$ Obviously $b = 1$ satisfies this. The key claim is that $b = (n-1)! + 1$ also satisfies this, which immediately shows that $a$ is not unique. To see why. write $b^n - 1 = (b-1)(b^{n-1} + b^{n-2} + \dots + b + 1) = ((n-1)! + 1 - 1)(b^{n-2} + \dots + b + 1).$ The left factor becomes $(n-1)!,$ and $(n-1)! \equiv 0 \pmod{n}$ since $n$ is composite, so the right factor is $1^{n-2} + \dots + 1 + 1 \equiv 0 \pmod{n}.$ So the entire product is divisible by $n!,$ implying that $a = (n-1)! + 1$ works, as claimed. Thus all composite $n$ don't work.

Therefore, only prime $n$ work, as desired.

Remark: A simpler proof that even $n > 2$ don't work is that $n! \equiv 0 \pmod{3}$ while $a^n + 1 \equiv 1,2 \pmod{3}.$

This post has been edited 2 times. Last edited by EpicBird08, Oct 13, 2024, 10:47 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

L13832

258 posts

L13832

#69 h Oct 31, 2024, 7:19 AM • 1 Y

Y by alexanderhamilton124

It is easy to see that $\boxed{n=1}$ work. We consider the case for $n$ even, so $a^n+1\equiv 2\pmod{3}$ so $\boxed{n=2}$ .
If $n$ is odd we consider $2$ cases, for odd primes and odd composites, here $a=n!-1$ satisfies the conditions of the problem, now we check for $a=(n-1)!-1$ , $((n-1)!-1)^n+1\equiv -1+1 \equiv 0\pmod{n!}$ , here we used the fact that $((n-1)!)^r\equiv 0\pmod{n!}, r\geq 2$ , but note that this contradicts the uniqueness of $a$ .
If $n$ is an odd prime $\text{ord}_{n!}(a)=2, 2n$ , if $\text{ord}_{n!}(a)=2$ then $n!\mid a+1$ so a valid construction for $a$ can be $n!-1$ . Hence $\boxed{\text{all odd primes n}}$ work. For $\text{ord}_{n!}(a)=2n$ we let $p$ be a prime such that $p\mid n!$ , then $\text{ord}_{n}(a)\mid p-1$ which is simply not possible.

This post has been edited 1 time. Last edited by L13832, Oct 31, 2024, 8:29 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Vedoral

89 posts

Vedoral

#70 h Nov 29, 2024, 3:26 PM

Y by

Click to reveal hidden text

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

SimplisticFormulas

90 posts

SimplisticFormulas

#71 h Feb 4, 2025, 12:33 PM • 1 Y

Y by teomihai

cool nt
soln

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

cursed_tangent1434

579 posts

cursed_tangent1434

#72 h Apr 5, 2025, 4:52 PM • 1 Y

Y by ihategeo_1969

Cool Problem! We claim that the answer is exactly the primes. We first show that all primes indeed do work.

When $n=2$ clearly $a=1$ is the only solution so the result is clear. When $n=p$ is an odd prime,
$(p!-1)^p+1 \equiv (-1)^p +1 \equiv 0 \pmod{p!}$ so $a=p!-1$ is a solution. Now, say $x$ is a positive integer in the given range such that $p! \mid x^p+1$ . Then,
$x^p \equiv -1 \pmod{p!}$ So $\text{ord}_{p!}x \mid 2p$ but $\text{ord}_{p!}x \nmid p$ . Thus, $\text{ord}_{p!}x=2$ or $\text{ord}_{p!}x=2p$ . However, $p \nmid \varphi(p!)$ which is a clear contradiction if $\text{ord}_{p!}x = 2p \mid \varphi(p!)$ . Thus, $\text{ord}_{p!}x=2$ which implies that $x^2 \equiv 1 \pmod{p!}$ . Hence,
$0 \equiv x^p+1 \equiv x+1 \pmod{p!}$ which implies that $x = p!-1$ as desired.

Now, note that all even $n>2$ do not work since if $n! \mid a^n+1$ then $n! \mid (n!-a)^n+1$ as well. These coincide if and only if $a = \frac{n!}{2}$ which is clearly impossible since then $\gcd(a,n)>1$ contradicting the fact that $n! \mid a^n+1$ . Thus, all even $n$ have zero or at least two working values for $a$ which is a contradiction.

We finally handle odd composite integers $n$ . Once again, $a=n!-1$ satisfies the desired divisibility. Note that
$((n-1)!-1)^n+1 \equiv (-1)^n+1 \equiv 0 \pmod{(n-1)!}$ Thus, we only need to look at primes dividing $n$ . Here, say odd $p \mid n$ . Since $n$ is not a prime $p \le n-1$ . Thus, $p \mid (n-1)!$ . Now, by Lifting the Exponent Lemma we have
$\nu_p(((n-1)!-1)^n+1) = \nu_p((n-1)!)+\nu_p(n)=\nu_p(n!)$ which implies that $n! \mid ((n-1)!-1)^n+1$ which contradicts uniqueness.

Z K Y