| | |
Find the remainder when $97!$ is divided by $101$.
Note, as $101$ is prime, we know that $100! \equiv -1\pmod{101}$. However, the left side has more factors than we want. Write this instead as $$97! \cdot 98 \cdot 99 \cdot 100 \equiv -1\pmod{101}$$ or equivalently, $$97! \cdot (-3)(-2)(-1) \equiv -1\pmod{101}$$ or more simply still $$97! \cdot (-6) \equiv -1\pmod{101}$$ All that remains is to find $(-6)^{-1}$, which is revealed to be $84$ after using the Euclidean Algorithm and back-solving, and multiply both sides by this value to find $$97! \equiv -84 \equiv 17\pmod{101}$$
Find the remainder when $2016! - 2015!$ is divided by $2017$.
$$\begin{align*} 2015! &\equiv 2016! \cdot 2016^{-1}\pmod{2017}\\ &\equiv (-1) \cdot (-1)^{-1}\pmod{2017}\\ &\equiv (-1) \cdot (-1)\pmod{2017}\\ &\equiv 1 \end{align*}$$ Thus, $2016! - 2015! \equiv -1 - 1 = -2 \equiv 2015\pmod{2017}$.
Prove $(p-2)! \equiv 1\pmod{p}$, when $p$ is prime.
If $p$ is prime, then by Wilson's Theorem, we know $(p-1)! \equiv -1 \equiv p-1\pmod{p}$.
As $p$ and $p-1$ are relatively prime, note $(p-1)$ has a multiplicative inverse$\pmod{p}$. Multiplying by this on both sides yields the desired congruence: $(p-2)! \equiv 1\pmod{p}$
Prove that if $n$ is a composite integer greater than $4$, then $(n-1)! \equiv 0\pmod{n}$
Proof by cases.
Case 1: If $n$ is not a perfect square, then we can find integers $a$ and $b$ with $1 \lt a,b \lt n$ and $a \neq b$, where $n = ab$. But given the bounds on $a$ and $b$, they are both present as factors in the expansion of $(n-1)!$. Thus, their product $n$ divides $(n-1)!$ and consequently $(n-1)! \equiv 0\pmod{n}$.
Case 2: If $n$ is a perfect square, then recall $n \gt 4$, so we can find $k \gt 2$, where $n=k^2$. Again, keeping in mind $k \gt 2$ note that their must be at least two multiples of $k$ in the expansion of $(n-1)!$, namely $k$ and $2k$. However, this means $k^2 \mid (n-1)!$ and thus $n \mid (n-1)^2$. We again have shown the necessary result.
🔎 Find the remainder upon division by 13 of $a$, where $$\frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{23} = \frac{a}{23!}$$
Put this back into the realm of integers by multiplying by $23!$.
🔎 For $\displaystyle{q = \frac{p-1}{2}}$, where $p$ is an odd prime, prove $\displaystyle{p \mid (q!)^2 + (-1)^q}$
Notice that$\pmod{p}$, we have $$\begin{align*} p-1 &\equiv -1\\ p-2 &\equiv -2\\ &\vdots\\ \frac{p+1}{2} &\equiv -\frac{p-1}{2} \end{align*}$$
🔎 Suppose $p \equiv 1\pmod{4}$, then show there exists an integer $n$ where $p \mid n^2 + 1$.
Could this be a special case of another result?