co.combinatorics – Probability of satisfying the congruent mod equation


I’m wondering about the probability of picking three different numbers $x,y,z$ out of the set $(50)=left{ 1,2,3,…,50right}$ satisfying the equation: $$xyzequiv gcd(x,y,z)mod 7$$ I started out by identifying a set of possible events $Omega$ that is, the set of all three-element subsets. Cardinality $|Omega|={50 choose 3}$. But I have trouble determining the cardinality of the set of favorable events: $$mathcal{M}=left{ left{ x,y,zright}inOmega: xyzequiv gcd(x,y,z)mod 7 right} $$
My efforts and observations:

  1. Some simplification of congruent mod equation.

Because $gcd(x,y,z)|x & gcd(x,y,z)|y & gcd(x,y,z)|z$, it will take place: $$text{gcd}^3(x,y,z)|xyz$$
So there is $x’,y’,z’$ such that $xyz=text{gcd}^3(x,y,z)x’y’z’$ so the equation can be written: $$xyzequiv gcd(x,y,z)mod 7$$ $$text{gcd}^3(x,y,z)x’y’z’equiv gcd(x,y,z)mod 7$$ $$gcd(x,y,z)left( text{gcd}^2(x,y,z)x’y’z’-1right)equiv 0mod 7$$ $7$ as it is prime, this should be equivalent:
$$gcd(x,y,z)equiv 0mod 7 text{OR} text{gcd}^2(x,y,z)x’y’z’equiv 1mod 7$$ The first congruence is satisfied when $x,y,z$ are multiples of $7$. In the set $(50)$ is $leftlfloor frac{50}{7} rightrfloor=7$ multiples of $7$. So the first congruence is satisfied for ${7 choose 3}=35$ such threes $x,y,z$. How to calculate how many numbers satisfy the second congruence is more problematic for me.

  1. Numerical calculations

I wrote a program that counts these triples that satisfy the congruence. The program counted: $$|mathcal{M}|=2079$$ I have tried to notice a pattern in the solutions. For example, I researched what $gcd$ are possible for threes that belong to $mathcal{M}$:

enter image description here
3. Generalization of the problem

I was thinking about making a generalization to any set $(n)$. Then let $|Omega_n|={n choose 3}$ and: $$mathcal{M}_n=left{ left{ x,y,zright}inOmega_n: xyzequiv gcd(x,y,z)mod 7 right} $$ And we are looking for: $$mathscr{P}(mathcal{M}_n)= frac{left| mathcal{M}_nright| }{left| Omegaright| } = frac{left| mathcal{M}_nright| }{ {n choose 3} } $$ Using the earlier program, I drew the distribution $mathscr{P}(mathcal{M}_n)$ vs $n$:
enter image description here
It turns out that local minima occur in arithmetic intervals and occur for $n=5,12,19,26,33,40,47,…$ rather, it is not a coincidence that this sequence differs $7$. In contrast, local maxima occur for $n=4,11,18,25,32,39,46,…$ the question of the limit of the sequence $mathscr{P}(mathcal{M}_n)$ also seems interesting: $$ lim_{n to infty } mathscr{P}(mathcal{M}_n)approxfrac{539}{5000}$$ although I’m more interested in how to solve this problem analytically.

Best regards MK