Congruence modulo 7

Question

I have a problem on the congruence of a rather particular quotient to which I cannot see the favorable outcome. What is the remainder of the Euclidean division of $\frac{(7n!)}{7^n\cdot n!}$ by $7$. My reasoning is as follows:

-Let $r$ be the remainder of this Euclidean division.

-We have to ask for the value $r$ between $0$ and $6$ included between $0$ and $6$ inclusive such that : $$\frac{(7n)!}{7^n×n!}\equiv{r}[7]$$

-We can see that the numbers $(7n)!$ and $7^n×n!$ are both multiples of $7$ , so they are by definition congruent to $0$ modulo $7$.

-Thus, the remainder of this Euclidean division $r$ is $r=0$.

(But I doubt very much that this is the case)

Answer 1

This can be solved by looking at the numerator differently. As, \begin{align} (7n)! &= (7n \cdot (7n-1) \cdots (7n-6)) \cdot ((7n-7) \cdot (7n-8) \cdots (7n-13)) \cdots (7 \cdot 6 \cdots 1) \\ &= 7^n (n \cdot (7n-1) \cdots (7n-6)) \cdot ((n-1) \cdot (7n-8) \cdots (7n-13)) \cdots (1 \cdot 6 \cdots 1) \\ &= (7^n)(n!)((7n-1) \cdots (7n-6)) \cdot ((7n-8) \cdots (7n-13)) \cdots (6 \cdots 1). \end{align} So the quotient becomes, $((7n-1) \cdots (7n-6)) \cdot ((7n-8) \cdots (7n-13)) \cdots (6 \cdots 1).$ Taking indices $\pmod{7}$ and applying Wilsons theorem (or simple inspection for $7$), \begin{align} ((7n-1) \cdots (7n-6)) \cdot ((7n-8) \cdots (7n-13)) \cdots (6 \cdots 1) &\equiv (6!)^n \\ &\equiv (-1)^n \pmod{7}. \end{align}

The issue with you logic is you are assuming that as $7$ divides both numerator and denominator, it must divide the quotient. This is not true, as the factors of 7 in the numerator and denominator perfectly cancel in this case.

Answer 2

The answer is that $r=1$ if $n$ is even and $r=-1$ (or 6, it's equivalent) if it's odd.

The problem can be solved as follows. First of all, let's determine the ratio between the expression:

$$\frac{[7(n+1)]!}{7^{n+1}×(n+1)!}$$

and the expression:

$$\frac{(7n)!}{7^n×n!}$$

The result will be: $$(7n+6)(7n+5)(7n+4)(7n+3)(7n+2)(7n+1)$$ which is congruent to $(6!)\pmod{7}$, which is, according to Wilson's Theorem, congruent to $-1\pmod{7}$. Since, conversely, $$\frac{(7n)!}{7^n×n!}×(7n+6)(7n+5)(7n+4)(7n+3)(7n+2)(7n+1)=\frac{[7(n+1)]!}{7^{n+1}×(n+1)!}$$ it follows that $$r(n+1)=-r(n)$$ and therefore $$r(n+2)=r(n)$$ We can now prove that $r=1$ for even values of $n$ and $r=-1$ for odd values of $n$. Since $r(0)=1$ and $r(1)=-1$, it follows that for any value of $k$, $r(2k)=1$ and $r(2k+1)=-1$