3
$\begingroup$

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.

This question may be helpful.

$\endgroup$
  • $\begingroup$ Isn't 11 prime...? $\endgroup$ – TMM Feb 13 '17 at 16:17
  • $\begingroup$ You start by asking if $f(n)=n-2$ when $n$ is prime, but then you immediately give a counterexample! $\endgroup$ – Barry Cipra Feb 13 '17 at 16:25
  • $\begingroup$ 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. $\endgroup$ – Robert Soupe Feb 13 '17 at 16:59
  • $\begingroup$ @RobertSoupe no OEIS exists but thanks for suggesting. $\endgroup$ – J. Linne Feb 13 '17 at 17:27
  • $\begingroup$ $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$. $\endgroup$ – Barry Cipra Feb 13 '17 at 17:45
5
$\begingroup$

Another result along the lines of the one in the OP's link is the following:

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$$

$\endgroup$
  • $\begingroup$ 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] $\endgroup$ – Catalin Zara Feb 14 '17 at 3:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.