Find all positive integers $n$ satisfying $2n+7 \mid n! -1$.
Problem
Source: Turkey JBMO Team Selection Test 2013, P6
Tags: modular arithmetic, number theory, number theory proposed
31.05.2013 23:05
First of all we can check case $n=1,2,3$ by hand where $n=1$ is solution. It is obvious $2n+7$ is prime , because if there is a prime $q$ such that $ q|2n+7 $ so we should have $q|n!-1$ which is contradiction with $q<n! , q|n!$ Now use Wilson's theorem we have : $\left( \frac{p-7}{2} \right) ! \equiv 1 \pmod{p} \implies (-1)^{\frac{p-7}{2}}(-9)(-25) \equiv 64 \pmod{p}$ Now suppose 2 case : Case 1 : $p \equiv 3 \pmod{4} $ this implies : $225 \equiv 64 \pmod{p} \implies p|161 \implies p=7,23$ so we can get $n=8$ which is solution. Case 2 : $p \equiv 1 \pmod{4} $ this implies : $64 \equiv -225 \pmod{p} \implies p|289 \implies p=17$ so we can get $n=5$ which is solution So we have 3 answer : $n=1,5,8$
02.06.2013 12:09
thanks, my friend. Here, my solution: (it's similar to your solution.) War-Hammer wrote: First of all we can check case $n=1,2,3$ by hand where $n=1$ is solution. It is obvious $2n+7$ is prime , because if there is a prime $q$ such that $ q|2n+7 $ so we should have $q|n!-1$ which is contradiction with $q<n! , q|n!$ But, I don't understand. We have $n\ge 7.$ Case 1: if at $n\in [1,6]$, we have two solution $n={1,5}$. Case 2: suppose that $n\ge 7.$ So $2n+7=p$ is prime and $p\ge 21$. Since Wilson's theorem, we get that \[ 225+(-1)^n \cdot 64 \equiv 0 \pmod{p}. \] Hence, $p=23$ and $n=8$. Answer: $n=\{1,5,8 \}.$
02.06.2013 12:27
Where you can't understand ??? If $2n+7$ is not prime , there is a prime $q$ such that $q|2n+7|n!-1$ , but from $n \ge 5$ we can get $q|n!$ which is contradiction.
02.06.2013 20:37
if $2n+7$ is not prime, there is a prime $q$ \[ n<q\le \frac{2n+7}{3} \] and \[ n < 7.\]
02.06.2013 20:53
But there is no solution for $ n=4,6 $
03.06.2013 07:35
You have small mistake. why? $n=5$ is solution.
03.06.2013 09:51
mathuz wrote: ... Since Wilson's theorem, we get that $225+(-1)^n \cdot 64 \equiv 0 \pmod{p}$ ... Let him without a sin throw the first stone. Your relation is wrong; it should be $225 - (-1)^n \cdot 64 \equiv 0 \pmod{p}$. And neither of you shows the details of getting this, which is in fact the core of the problem, by using $64(n+1)(n+2)(n+3)(n+4)(n+5)(n+6) \equiv - 225 \pmod{2n+7}$ and $(n+7)(n+8)\cdots (2n+6) \equiv (-1)^n n! \pmod{2n+7}$.
03.06.2013 10:56
ow, sorry, you are right. I have a mistake!
03.06.2013 11:57
This problem has been discussed also at http://www.artofproblemsolving.com/Forum/viewtopic.php?f=56&t=535792
04.07.2021 22:39
how in the world did i miss n=1 First, observe that $n=1, 5$ work and nothing else works for $n<7$. Now, we assume $n\geq 7$. Note that if $2n+7$ is not prime, then its second greatest prime factor is at most \begin{align*} \frac{2n+7}{d}\leq\frac{2n+7}{3}\leq n, \end{align*}which is a contradiction as $2n+7$ cannot divide any number less than $n$. Hence, $2n+7$ is prime. Therefore, by Wilson, \begin{align*} -1&\equiv(2n+6)!\pmod{2n+7} \\ -1 &=n!\cdot (n+1)\cdot (n+2)\cdot (n+3)\cdot (n+4)\cdot (n+5)\cdot (n+6)\cdot (-1)^n\cdot n!\pmod{2n+7} \\ -64&\equiv \cdot (4n^2+28n+24)\cdot(4n^2+28n+40)\cdot(4n^2+28n+48)\cdot(-1)^n\cdot (n!)^2\pmod{2n+7} \\ 64&\equiv225(-1)^n\pmod{2n+7}. \end{align*}If $n$ is odd, then $2n+7\mid 289$. Since $2n+7$ is prime, then $2n+7=17$ so $n=5$. If $n$ is even, then $2n+7\mid 161$ so either $2n+7=7$ or $2n+7=23$. The first case is impossible and the second case gives $n=8$, which works. To conclude, the only solutions are $n=1, 5, 8$.
25.08.2021 08:13
Since $n=1$ works assume that $n>1$ Claim 1:- $2n+7$ is a prime. Proof:- If $2n+7$ is a composite, then $(2n+7)^2 \ge (n+1)^2$ and so $n^2 \le 6$ or $n=2$ which doesn't work. Now by Wilson's theorem we have : $\left( \frac{p-7}{2} \right) ! \equiv 1 \pmod{p} \implies (-1)^{\frac{p-7}{2}}(-9)(-25) \equiv 64 \pmod{p}$ So we have 2 cases:-. Case 1:-$p \equiv 3 \pmod{4} $ this implies : $225 \equiv 64 \pmod{p} \implies p|161 \implies p=7,23$ so we can get $n=8$ which works. Case 2:- $p \equiv 1 \pmod{4} $ this implies : $64 \equiv -225 \pmod{p} \implies p|289 \implies p=17$ so we can get $n=5$ which works. Hence all the solutions are $n=1,5,8$
27.07.2022 07:02
Notice $n!\equiv 1\pmod{2n+7}$ so $\gcd(2n+7,i)=1$ for all $1\le i\le n.$ Hence, all the prime divisors of $2n+7$ must be in the range $[n+1,2n+7].$ Suppose $2n+7$ is composite. Then, $pq\mid 2n+7$ for two (not necessarily distinct) primes $p,q\in[n+1,2n+7],$ so $$2n+7\ge (n+1)(n+2)\implies 2n+7\ge n^2+3n+2\implies 5\ge n^2+n.$$Hence, $n=1$ so $2n+7=9$ and $9\mid 1!-1=0,$ which works. Now, suppose $p=2n+7$ is an odd prime. Then, $n=\tfrac{p-7}{2}$ and we see $$\left(\frac{p-7}{2}\right)!\equiv 1\pmod{p}.$$Also, $i\equiv -(p-i)\pmod{p}$ so $-1=(p-1)!=(-1)^{\frac{p-1}{2}}\left(\left(\frac{p-1}{2}\right)!\right)^2\pmod{p}$ by Wilson's theorem. Hence, $$\pm 1\equiv\left(\left(\frac{p-7}{2}\right)!\cdot\frac{p-5}{2}\cdot\frac{p-3}{2}\cdot\frac{p-1}{2}\right)^2\equiv\left(\frac{(-3)(-5)(-1)}{8}\right)^2\pmod{p}.$$This means $225\equiv\pm 64\pmod{p},$ so $p\mid 289$ or $p\mid 161.$ Hence, $p=17,7,23.$ If $p=17,$ then $n=5$ and $17\mid 5!-1=119.$ If $p=7,$ then $n=0,$ which is a contradiction. If $p=23,$ then $n=8$ and $$8!\equiv 8\cdot 7\cdot 6\cdot 5\cdot 4!\equiv 56\cdot 30\equiv 10\cdot 7\equiv 70\equiv 1\pmod{23}.$$Therefore, all three primes work and our solutions are $n=\boxed{1,5,8}.$
14.04.2023 02:18
$n=1$ works, so assume $n>1$. Then, for all $p \mid 2n+7$, $p \mid n!-1$ so $p \geq n+1$. If $2n+7$ is composite, then $2n+7 \geq (n+1)^2$, so $n \leq 2$, which doesn't work. Thus, $p = 2n+7$ is prime. We know $$\left(\frac{p-1}2\right)! \equiv 1 \pmod p,$$but this implies that $\left(\frac{p+5}2\right)^2 = (-1)^{(p-9)/2}4, hence $64(-1)^{(p-7)/2} \equiv 225 \pmod 4$. This yields $n \in \{1, 5, 8\}$ are the solutions.
24.07.2023 06:49
First suppose that $2n+7$ is composite, so that there exists some prime factor $p$ of $2n+7.$ Then there must exist some positive integer $k>1$ such that $pk=2n+7$. Because $2n+7=2(n+3)+1$ is odd, we must have $k\neq2$, implying that $k\ge3$ and thus $p\le\frac{2n+7}3.$ Now, $2n+7\mid n!-1$ implies that $p\mid n!-1$ and equivalently $n!\equiv1\pmod{p}.$ Because $n!\equiv0\pmod{i}$ for all $i\in\{1,2,\cdots,n\},$ it follows that $p\notin\{1,2,\cdots,n\}$ and therefore $n+1\le p.$ Combining this with the inequality $p\le\frac{2n+7}3$, as derived previously, gives $$n+1\le\frac{2n+7}3,$$or $3n+3\le 2n+7$ and equivalently $n\le4,$ so that $n\in\{1,2,3,4\}.$ Checking all four cases of $n$, we find that only the cases where $n=1$ works. It follows that we must have $n=1$ for composite $2n+7$. Thus, suppose that $n\ge5$, so that $2n+7\ge17$ is prime. Then we are given that $$n!\equiv1\pmod{2n+7},$$so that \begin{align*} (2n+6)!&\equiv n!(n+1)(n+2)\cdots(2n+6)\pmod{2n+7}\\ &\equiv n!((n+1)(n+2)\cdots(n+6))((-n)\cdots(-2)(-1))\pmod{2n+7}\\ &\equiv n!((n+1)(n+2)\cdots(n+6))(-1)^nn!\pmod{2n+7}\\ &\equiv(1)((n+1)(n+6))((n+2)(n+5))((n+3)(n+4))(-1)^n(1)\pmod{2n+7}\\ &\equiv(-1)^n(n^2+7n+6)(n^2+7n+10)(n^2+7n+12)\pmod{2n+7}. \end{align*}However, Wilson's Theorem implies that $$(2n-6)!\equiv-1\pmod{2n+7},$$so it follows that $$(-1)^n(n^2+7n+6)(n^2+7n+10)(n^2+7n+12)\equiv-1\pmod{2n+7}.$$Multiplying both sides by $64(-1)^{n+1}$ gives $$4^3(-1)^{2n+1}(n^2+7n+6)(n^2+7n+10)(n^2+7n+12)\equiv64(-1)^{n+2}\pmod{2n+7},$$or equivalently $$-(4n^2+28n+24)(4n^2+28n+40)(4n^2+28n+48)\equiv64(-1)^n\pmod{2n+7}.$$Observing that \begin{align*} 4n^2+28n&\equiv(4n^2+28n+49)-49\pmod{2n+7}\\ &\equiv(2n+7)^2-49\pmod{2n+7}\\ &\equiv-49\pmod{2n+7}, \end{align*}our equation $(4n^2+28n+24)(4n^2+28n+40)(4n^2+28n+48)\equiv64(-1)^{n+1}\pmod{2n+7}$ becomes \begin{align*} 64(-1)^n&\equiv-(-49+24)(-49+40)(-49+48)\pmod{2n+7}\\ &\equiv-(-25)(-9)(-1)\pmod{2n+7}\\ &\equiv225\pmod{2n+7}. \end{align*} If $n$ is even, then the above expression becomes $$64\equiv225\pmod{2n+7},$$or $2n+7\mid 225-64=161=7\cdot23,$ forcing us to have $n=\frac{23-7}2=8$ as $2n+7$ is prime and $n>0.$ If $n$ is odd, then we instead have $$-64\equiv225\pmod{2n+7},$$so that $2n+7\mid 225+64=289=17^2,$ implying that $n=\frac{17-7}2=5$; again, $n$ is prime. It is easy to check that both $n=5$ and $n=8$ work; combined with the solution $n=1$ for composite $2n+7$, we conclude that the only values of $n$ for which $2n+7\mid n!+1$ are $1$, $5$, and $8.$ $\blacksquare$