4
$\begingroup$

While solving problems in the theory of congruence, I came across the following problem: Prove that for each $k\in \mathbb{N}$ there exists $k$ consecutive composite positive integers.

Now the solution to the above problem is to consider $(k+1)!+2, \cdots, (k+1)!+(k+1)$ and to show that each of them is composite.

After this, while i was checking the primality of $20!+18, 20!+19, \cdots, 20!+23$ i got stuck at 20!+23. All those previous numbers were easy to show they were composite but I found no elementary approach to show $20!+23$ is composite.

How can we show that this number is composite using elementary techniques from the theory of congruence ?

$\endgroup$
7
  • $\begingroup$ It divisible by $37$. The rest is obvious. $\endgroup$ Sep 3, 2017 at 11:32
  • $\begingroup$ Check divisibility by primes larger than 20: ... 23, 29, ... pretty soon you will get one that works. $\endgroup$
    – GEdgar
    Sep 3, 2017 at 11:32
  • 3
    $\begingroup$ Note that the argument solution you're quoting stops at $20!+20$. It is just coincidence that $20!+21$ and $20!+22$ happen to be composite, and equally a coincidence that $20!+23$ is. $\endgroup$ Sep 3, 2017 at 11:47
  • 1
    $\begingroup$ oeis.org/A037152 might be of interest. $\endgroup$ Sep 3, 2017 at 12:09
  • 1
    $\begingroup$ See oeis.org/A037153 also. $\endgroup$ Sep 3, 2017 at 12:34

3 Answers 3

3
$\begingroup$

Note that $20!$ is divisible by $14\equiv -23$ modulo $37$. Show that $20!/14\equiv 1$ modulo 37.

P.S. In order to find the prime 37, try prime $p \in (23,23+20]$ and check if $20!/(p-23)-1$ is divisible by $p$.

$\endgroup$
5
  • $\begingroup$ Why that interval ? Is there any special formula to find such ? $\endgroup$
    – KON3
    Sep 3, 2017 at 11:46
  • $\begingroup$ @Anjan3 No prime $\leq 23$ works because $20!+23\equiv 0$ modulo $p$. The upper bound is just to be sure that $20!/(p−23)$ is an integer. $\endgroup$
    – Robert Z
    Sep 3, 2017 at 11:56
  • $\begingroup$ Kindly please help me. I am unable to understand. 20! is divisible by 14. And 14 $\equiv$ -23 mod 37. Why should we show $(20! / 14) \equiv 1 (mod 37)$ ? $\endgroup$
    – KON3
    Sep 7, 2017 at 1:18
  • $\begingroup$ @Anjan3 If so $20!/14\cdot 14+23\equiv 1\cdot (-23) +23=0$ modulo $37$. $\endgroup$
    – Robert Z
    Sep 7, 2017 at 4:15
  • $\begingroup$ Indeed, why that interval? There are primes $p\in(31,31+20]$, but none of them divide $n=20!+31$, but $n$ is composite. $\endgroup$
    – Rosie F
    Nov 25, 2017 at 16:37
2
$\begingroup$

HINT: Show that $$20!\equiv 14\mod 37$$

$\endgroup$
2
  • 3
    $\begingroup$ I know it is divisible by 37. But suppose we don't know that. Then how to prove the number is composite ? $\endgroup$
    – KON3
    Sep 3, 2017 at 11:34
  • $\begingroup$ thats the Problem i would try prime numbers $$2;3;5;7;11;13;...$$ and so on, how found Euler the number $641$ which is is a factor of $$4294967297$$? $\endgroup$ Sep 3, 2017 at 11:38
0
$\begingroup$

Let $20!+23$ divisible by $p$, where $p$ is a prime.

Thus, $p>23$ and we need to check $p\in\{29,31,37\}$ and checking of $p=37$ gives that $20!+23$ is a composite number.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .