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$
  • $\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 Sep 11 '17 at 21:23
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ dont see why not i mean it cant be even but i dont know that k+1 is even $\endgroup$ – Faust Sep 9 '17 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 Sep 9 '17 at 23:51
  • $\begingroup$ Oh im an idiot thanks. Will accept once it lets me $\endgroup$ – Faust Sep 9 '17 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
    $\begingroup$ You don't even need the similar argument for $b$: if $a=1$ then $b = Q_n > n$. $\endgroup$ – Peter Taylor Sep 11 '17 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$

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.