0

Let $S$ be the number of possible solutions for the formula below

$$a * b \equiv c \pmod{x}$$

Where $a,b,c,x \in \mathbb{Z}$ and $0 < a \leq b < x$

I would like to find $c$ and $x$ for which $S/x$ will be the smallest. I tested all the $c$ and $x$ values from $5<x<1,000,000; c < x$ and found that the top smallest $S$ numbers are:

  • $x=2*3; c=5; S = 0.16666666666666666$
  • $x=2*3*5; c=7; S = 0.13333333333333333$
  • $x=2*3*5*7; c=11; S = 0.11428571428571428$
  • $x=2*3*5*7*11; c=13; S = 0.1038961038961039$
  • $x=2*3*5*7*11*13; c=17; S = 0.0959040959040959$
  • $x=2*3*5*7*11*13*17; c=19; S = 0.09026267849797262$

With this clear pattern of prime number series, is there any efficient way to calculate $S$ for bigger numbers?

Taylor Rendon
  • 2,276
Ilya Gazman
  • 1,440

1 Answers1

1

You can use Euler's totient function to show that:

If $x$ a product of the initial distinct primes, i.e. $x=\prod p_i$, and if $c$ is coprime to $x$, then $$S=\frac1{2x}\prod\left(p_i-1\right)$$

Henry
  • 157,058
  • For some reason it only much my first result of $0.166$, can you please check if my results are munching? – Ilya Gazman Jul 04 '20 at 02:20
  • 1
    @IlyaGazman: In your last example, $x=\prod p_i= 2\times 3\times 5\times 7\times 11\times 13\times 17=510510$ while $\prod\left(p_i-1\right)=1\times 2\times 4\times 6\times 10\times 12\times 16 = 92160$ and $\frac{92160}{2\times 510510}\approx 0.090262678$ as you found – Henry Jul 04 '20 at 09:32