The recent post didn't really provide sufficient help. It was too vague, most of it went over my head.
Anyway, I'm trying to find the $\gcd(n!+1,(n+1)!)$.
First I let $d=ab\mid(n!+1)$ and $d=ab\mid(n+1)n!$ where $d=ab$ is the GCD.
From $ab\mid(n+1)n!$ I get $a\mid(n+1)$ and $b|n!$.
Because $b\mid n!$ and $ab\mid(n!+1)$, $b$ must be 1.
Consequently, $a\mid(n!+1)$ and $a\mid(n+1)$.
So narrowing down options for $a$ should get me an answer. At this point I've tried to somehow bring it around and relate it to Wilson's theorem as this problem is from that section of my textbook, but I seem to be missing something. This is part of independent study, though help of any kind is appreciated.
Answer
The previous posts have I think carefully explained why the gcd is $1$ if $n+1$ is composite. It comes down to this: if $q$ is a prime that divides $(n+1)!$, and $n+1$ is composite, then $q \lt n+1$, and therefore $q \le n$. But then $q$ divides $n!$, and therefore $q$ cannot divide $n!+1$.
You have shown that any common divisor of $n!+1$ and $(n+1)!$ must divide $n+1$.
Suppose now that $n+1$ is prime, say $n+1=p$. Then by Wilson's Theorem, $(p-1)!\equiv -1 \pmod p$. This says that $p$ divides $(p-1)!+1$, meaning that $n+1$ divides $n!+1$.
It follows that if $n+1$ is prime, then $n+1$ is a common divisor of $n!+1$ and $(n+1)!$. It is the greatest common divisor, since all common divisors must divide $n+1$, and nothing bigger than $n+1$ can divide $n+1$.
We conclude that $\gcd(n!+1,(n+1)!)=1$ if $n+1$ is composite, and $\gcd(n!+1,(n+1)!)=n+1$ if $n+1$ is prime.
No comments:
Post a Comment