# 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}$$: 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$$: 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 Posted on