# Number of consecutive integers such that the product is $1$ $\pmod n$

Define a function for $n$ $>$ $1$ which is $f(n)$ $=$ $k$, the maximum number of consecutive integers such that their product is $1$ $\pmod n$, and every integer $1 \leq x \leq k$, there exists $x$ consecutive integers such that their product is $1$ $\pmod n$.

For prime $n$, does $f(n)$ $=$ $n-2$?

Example (not a counterexample for the question above);

$n=11$, $f(11)$ $=$ $3$ because there are $1, 2, 3$ consecutive integers such that their product is $1$ $\pmod{11}$. But there are no $4$ consecutive integers such that their product is $1$ $\pmod {11}$. There are $9$ consecutive integers such that their product is $1$ $\pmod {11}$, but $f(11)$ $=$ $3$ due to the fact that the product of $4$ consecutive integers is never $1$ $\pmod {11}$.

$(1)$ $=$ $(1)$ $\pmod {11}$

$(3 \times 4)$, $(8 \times 7)$ $=$ $1$ $\pmod {11}$

$(5 \times 6 \times 7)$ $=$ $1$ $\pmod {11}$

Can anyone list some extraordinarily large values for $f(n)$, compared to most values of $f(n)$? The example is the largest I could come up with. Thanks for help, feedback, etc.

• Isn't 11 prime...? – TMM Feb 13 '17 at 16:17
• You start by asking if $f(n)=n-2$ when $n$ is prime, but then you immediately give a counterexample! – Barry Cipra Feb 13 '17 at 16:25
• What I would do is figure out $f(n)$ for $2 \leq n \leq 10$ to obtain a sequence of integers and then look that up in the OEIS. – Robert Soupe Feb 13 '17 at 16:59
• @RobertSoupe no OEIS exists but thanks for suggesting. – J. Linne Feb 13 '17 at 17:27
• $f(n)=1$ when $n$ is even. For odd $n$, $f(n)\le p-2$ where $p$ is the smallest prime divisor of $n$. So it would make sense to focus first on $f(p)$ for odd primes $p$. The OP's link shows that $f(p)=1$ if and only if $p\equiv\pm2$ mod $5$. – Barry Cipra Feb 13 '17 at 17:45

Statement: If $p$ is prime and $f(p) > 3$, then $p \equiv \pm 1 \pmod{8}$.
Proof: Suppose $f(p) \geqslant 4$; then there exist 4 consecutive integers whose product is 1 mod $p$: $$(k-1)k(k+1)(k+2) \equiv 1 \pmod{p}.$$
Simple algebraic manipulations show that the above is equivalent to $$(k^2+k-1)^2 \equiv 2 \pmod{p},$$ hence 2 is a quadratic residue modulo $p$, which implies that $p \equiv \pm 1 \pmod{8}$.
Hence to get large values of $f(p)$, it suffices to check primes $p$ that are $\pm 1 \pmod{8}$ and $\pm 1 \pmod{5}$, hence $\pm 1$ or $\pm 9 \pmod{40}$. My computer tells me that of the first 50000 primes, the maximum value of $f(p)$ is $f(321721) = 15$, with $1, 2, 3, \ldots, 15$ runs starting respectively at at $$1, 46396, 240095, 51194, 37879, 124075, 94231, 137236, 142566, 31506, 193600, 140210, 234595, 121755, 12219$$
• Update: $f(551519) = 17$, with runs starting at [1, 35187, 54714, 88700, 216741, 5393, 80777, 107416, 320027, 10768, 89496, 128591, 119866, 187626, 393701, 88788, 112258] – Catalin Zara Feb 14 '17 at 3:59