6
$\begingroup$

Let $p_1, p_2, \ldots, p_n$ prime numbers such that for each $i, 1 \le i \le n$, $$\prod\limits_{j \neq i} p_j \equiv 1 \pmod{p_i}.$$ For example, $2,$ $3$ and $5$ satisfies these conditions. Then, it is true that one of $p_1, p_2, \ldots, p_n$ must be $2$?

$\endgroup$
  • 1
    $\begingroup$ Ha, I see how this is related to your previous question math.stackexchange.com/q/3541810/700480 ... Your condition implies that $p_1p_2\cdots p_n(1/p_1+1/p_2+\ldots+1/p_n)\equiv 1\pmod{p_1p_2\cdots p_n}$, so $1/p_1+1/p_2+\ldots+1/p_n$ must be very close to, but above, an integer, and it is quite hard to even get to $1$ without involving a lot of primes, especially if you are not allowed to use the prime number $2$. I don't know the answer, of course, but this sounds very interesting. $\endgroup$ – Stinking Bishop Feb 14 at 23:31
  • $\begingroup$ Also, do you (or anyone else) know about any other example except for $2,3,5$, containing $2$ or not? $\endgroup$ – Stinking Bishop Feb 14 at 23:35
  • $\begingroup$ @StinkingBishop (2,3,7,41) and (2,3,11,13) $\endgroup$ – ACheca Feb 14 at 23:49
  • 1
    $\begingroup$ Special (prime) case of this question on "Easy CRT" problems. $\endgroup$ – Bill Dubuque Feb 14 at 23:56
  • 1
    $\begingroup$ It every Giuga sequence has an even factor then this implies that no Giuga number is a Carmichael number (they're all odd), so this would prove Giuga's conjecture. Were you aware of this (well-known) relationship? $\endgroup$ – Bill Dubuque Feb 15 at 1:11
4
$\begingroup$

Just writing some interesting information related to the question here: OEIS has a list of solutions for this in A236434. The numbers made multiplying each list are called Giuga numbers. It seems that all known numbers are even (so there is no counterexample to your property), and if there is any, it has to have at least 14 different prime factors.

$\endgroup$
2
$\begingroup$

It is not what you are asking but you can make some conjecture on the density of solution, assuming independence and uniform distribution of congruences. Based on this you can do numerical experiments and compare with the truth.

Let $m=\prod_{j=1}^i p_j$ squarefree, if for some $q$ the set $\{ p_1,\ldots, p_i,q\}$ satisfies your condition then $q$ is the unique $a\in [1,m]$ such that $a \frac{m}{p_j}\equiv 1\bmod p_j$. Such a $a$ always exists, what is rare is that $a$ is prime and $m\equiv 1\bmod a$.

Thus we can estimate the probability that $m$ works as $\approx\frac1{\log m}\times \frac{\log m}m$ where $\frac1{\log m}$ is probability that $a$ is prime and $\frac{\log m}m\approx \Bbb{E}[\frac1a]$ is the probability that $m\equiv 1\bmod a$.

And hence the number of solutions with $m\le M$ is expected to be $$\approx \sum_{m\le M} \frac{|\mu(m)|}{m}\approx C \log M$$

$\endgroup$

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.