Need some guidance on a problem I'm trying to solve:
If n is $1, 2, 4$, or $6$ then $\frac{(n!-3)}{(n-3)}$ is an integer. The largest of
these numbers is $6$. What is the largest possible value of n for which
$\frac{(n!-123)}{(n-123)}$ is an integer?
I'm totally stumped on this. I tried brute force by substituting the '$123$' (let's call that $p$) with smaller numbers less than $10$ to see if there's a discernible pattern.
It seems to be the case that with smaller values of $p$, the equation is an integer when $n = 2p,$ which would suggest the answer is $246$. However I'm told this is incorrect.
I've also tried writing some Python code to test $n$ up to $999$, but the code craps out at $170$ as the factorial term is too large for floating point numbers.
I strongly believe there's a better way of solving this than brute force…but I'm stumped on which way to go here. I've been toying with 'if the expression is an integer then $(n!-123) = k(n-123)$ for some integer $k$, but this is getting me nowhere. I still don't know how to handle factorials algebraically.
Any pointers greatly appreciated!
Best Answer
So we want to find the biggest $k$, where
$$\frac{n!-123}{n-123} = k$$
Now, we can rearrange this to yield
$$n!-123 =k(n-123)$$
Now if $n > 123$ (we can do this since we are seeking for the largest $n$, and all smaller cases won't matter if we find a larger one), then
$$n!-123 \equiv n(n-1)\cdots(n-123)\cdots(3)(2)(1) -123 \equiv -123 \equiv 0 \pmod {n-123}$$
Thus, $$-123 \equiv 0 \pmod{n-123}$$
And the only way for this to work is if $123$ is a multiple of $n-123$. To find the largest $n$, we will need to take the largest factor. Thus, $123 = n-123$, and thus $n=246$ is the largest $n$.
In fact, the largest $K$ for $$\frac{N\hspace{0.5mm} ! -p}{N-p} = K$$ is actually $2p$, if we repeat the process above for all values.