3
$\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$
  • $\begingroup$ It divisible by $37$. The rest is obvious. $\endgroup$ – Michael Rozenberg Sep 3 '17 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 '17 at 11:32
  • $\begingroup$ Are you imagining that there are some general properties of the numbers $20$ and $23$ that could lead us to conclude directly that $20!+23$ is composite? What would those properties be? I cannot see any that would work, other than the fact that the number you get when you calculate $20!+23$ happens to be composite. $\endgroup$ – Henning Makholm Sep 3 '17 at 11:46
  • 2
    $\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$ – Henning Makholm Sep 3 '17 at 11:47
  • $\begingroup$ hmm....alright. I got it ! thanks :-) $\endgroup$ – Anjan3 Sep 3 '17 at 11:53
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$
  • $\begingroup$ Why that interval ? Is there any special formula to find such ? $\endgroup$ – Anjan3 Sep 3 '17 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 '17 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$ – Anjan3 Sep 7 '17 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 '17 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 '17 at 16:37
2
$\begingroup$

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

$\endgroup$
  • 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$ – Anjan3 Sep 3 '17 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$ – Dr. Sonnhard Graubner Sep 3 '17 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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.