For positive integers $a$ and $b$, define \[a!_b=\prod_{1\le i\le a\atop i \equiv a \mod b} i\] Let $p$ be a prime and $n>3$ a positive integer. Show that there exist at least 2 different positive integers $t$ such that $1<t<p^n$ and $t!_p\equiv 1\pmod {p^n}$.
Problem
Source: 2023 Serbia TST Problem 5
Tags: nt, Factorials, Weird, Serbia, TST, modular arithmetic, number theory
gvole
22.05.2023 17:49
My solution from contest (the only one lol):
If $p$ is odd, then $p^n-p+1$ and $p^n-p-1$ work.
The first one is just the product of all the residues which are $1 \pmod p$ , so it is equal to \[g^{p-1}g^{2(p-1)}\dots g^{(p^{n-1}-1)(p-1)}=g^{(p-1)p^{n-1}\frac{p^{n-1}-1}2}=1\]while the second one is all the residues which are $-1 \pmod p$ except for $-1$ which is equal to \[(-1)g^\frac{p-1}2 g^{p-1+\frac{p-1}2}\dots g^{(p^{n-1}-1)(p-1)+\frac{p-1}2}=(-1)g^{p^{n-1}\frac{p-1}2+p^{n-1}(p-1)\frac{p^{n-1}-1}2}=(-1)g^{p^{n-1}\frac{p-1}2}=1\]
When $p=2$ we first notice one thing: the product of all odd residues is 1 because there are exactly 4 solutions to $x=\frac 1{x}$, namely $1,-1,2^{n-1}-1,2^{n-1}+1$. This is clear by solving for $x^2-1=0$ and their product being 1. This means $2^n-1$ works.
Also, $(1\cdot3\cdot \dots \cdot 2^{n-1}-1)^2$ is exactly the product of all odd residues since we get an even number of $(-1)$'s (namely $2^{n-2}$).
This means that $1\cdot3\cdot \dots \cdot 2^{n-1}-1 = 1$ or $1\cdot3\cdot \dots \cdot 2^{n-1}-1=2^{n-1}+1$ since it is also $1$ mod $2^{n-1}$ by previous reasoning. In the first case we take $2^{n-1}-1$, and in the other case we take $2^{n-1}+1$, since then the value is $(2^{n-1}+1)^2=1$.