1
$\begingroup$

Show that the integer $Q_n = n! + 1$ where n is a positive integer, has a prime divisor greater than n.

if n! + 1 is prime we are done, if n! + 1 is not prime then it is composite this argument doesnt seem lead anywhere which points to induction.

base case n=1 1+1=2 2>1 true for base case assume true for kth case WTS true for k+1. $(k+1)k! +1 = kk! +k! +1 =a $

$kk! +k! +1 =a $ now by IH $k! +1$ has a divsior greater than or equal to k+1 now i want to assume that k+1 is relatively prime to kk! to show that the divisor must be at least k+2 which is > k+1 but i dont think i can?

Edit: each number $Q_n$ is the product of the first n integers +1 somewhere it says something to the effect that $Q_n$ is realtivly prime to every one of the integers in that list.

$\endgroup$
1
  • $\begingroup$ This is one of, apparently, infinitely many ways to prove there is no largest prime: If $p$ is prime then $p!+1$ is divisible by a prime greater than $p.$ $\endgroup$
    – DanielWainfleet
    Commented Sep 11, 2017 at 21:23

3 Answers 3

Reset to default
4
$\begingroup$

Hint: Can it have any prime divisors $\leq n$?

$\endgroup$
3
  • $\begingroup$ dont see why not i mean it cant be even but i dont know that k+1 is even $\endgroup$
    – Faust
    Commented Sep 9, 2017 at 23:50
  • $\begingroup$ Think about why it can't be even. Can you extend that argument to show that (when $n>2$) it is never a multiple of $3$? $\endgroup$
    – Carl Schildkraut
    Commented Sep 9, 2017 at 23:51
  • $\begingroup$ Oh im an idiot thanks. Will accept once it lets me $\endgroup$
    – Faust
    Commented Sep 9, 2017 at 23:52
4
$\begingroup$

Suppose that $Q_n$ is composite. Then there exists integers $a$ and $b$ such that $ab = Q_n$. If $a$ or $b \leq n$ then we have a problem. Let's say that $a \leq n$. Then $a$ divides both $n!$ and $n!+1$ which means that $a$ would be able to divide the difference $$(n!+1)-n!=1.$$ This implies $|a|=1$ and so we see that any divisor (prime or composite) will need to be larger than $n$.

$\endgroup$
1
  • 1
    $\begingroup$ You don't even need the similar argument for $b$: if $a=1$ then $b = Q_n > n$. $\endgroup$
    – Peter Taylor
    Commented Sep 11, 2017 at 13:43
1
$\begingroup$

Q cannot be divisible by any of 2, 3, 4, ... n. So Q is either prime itself or has a prime factor > n.

$\endgroup$

You must log in to answer this question.

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