# Diophantine equation with $gcd = 1$

John has $100$ marbles and wants to split them into $4$ groups $A,B,C,$ and $D$ such that the greatest common divisor of the number of marbles in all of the groups is $1$. Find the number of ways John can do this.

This question is equivalent to finding all nonnegative solutions to $x+y+z+w = 100$ if $\gcd({x,y,z,w}) = 1$. I am unsure how to solve such an equation in general or if there is a way to do it easily.

• Step 1: Forget about the $\gcd$ restriction and find the number of ways to split the marbles into four groups. Step 2: Count the number of ways to split the marbles into four groups such that the $\gcd$ of the group sizes is larger than $1$. – Daniel Fischer Jan 21 '16 at 23:24
• @DanielFischer Step 1: We have $\binom{103}{3}$ number of ways. Step 2: We must count the number of solutions where they all share a common factor greater than $1$. Thus, $A = kx, B = ky, C = kz, D = kw$. Thus, $k(x+y+z+w) = 100$. Here $k$ must be a multiple of $100$, thus $k = 2,5,10,25,50,100$. We also have the added condition that $\gcd(x,y,z,w) = 1$. – John Ryan Jan 21 '16 at 23:29
• That's one way, to use all divisors of $100$. You could also use the inclusion-exclusion principle (which makes for less work here). – Daniel Fischer Jan 21 '16 at 23:31
• @DanielFischer How do I deal with the restriction of $\gcd(x,y,z,w) = 1$? – John Ryan Jan 21 '16 at 23:35
• @DanielFischer For example, $x+y+z+w = 50$ if $\gcd(x,y,w,z) = 1$. I don't see an easy way to count that. – John Ryan Jan 21 '16 at 23:49

To count the number of solutions to problem $X$ that satisfy the additional condition $C$, it is often easier/more efficient to count all solutions of $X$ and then subtract the number of solutions that violate condition $C$. This is also the case here.

When we partition $n$ marbles into $k$ groups of sizes $s_1,\dotsc, s_k$, then $d := \gcd(s_1,\dotsc,s_k)$ is a divisor of $n$. If $d > 1$, then there is at least one prime $p$ that divides $d$. For a given prime $p$ dividing $n$, to count the number of partitions of $n$ marbles into $k$ groups such that the greatest common divisor of the group sizes is a multiple of $p$ amounts to counting the number of partitions of $n/p$ marbles into $k$ groups without any restriction on the group sizes.

Here, we have $n = 100$, with the only primes dividing $n$ being $2$ and $5$. So if the greatest common divisor of the group sizes is not $1$, it must be a multiple of $2$, or a multiple of $5$.

To find the number of partitions such that the greatest common divisor of the sizes is $1$, we take the number of all partitions of $100$ marbles into four groups and subtract the number of partitions of $\frac{100}{2} = 50$ marbles into four groups, and the number of partitions of $\frac{100}{5} = 20$ marbles into four groups. But now we have subtracted the partitions such that the greatest common divisor of the group sizes is a multiple of both, $2$ and $5$, twice. Hence we must then add the number of partitions of $\frac{100}{2\cdot 5} = 10$ marbles into four groups to get the final result.

In formulae:

$$N_1(100,4) = N(100,4) - N(100/2,4) - N(100/5,4) + N(100/10,4),$$

where $N(n,k)$ denotes the number of partitions of $n$ marbles into $k$ groups, and $N_1(n,k)$ denotes the number of partitions such that the greatest common divisor of the group sizes is $1$.

Generally:

$$N_1(n,k) = \sum_{d\mid n} \mu(d)\cdot N(n/d,k)$$

where $\mu$ is the Möbius function.

• I get the answer to be $151940$. – John Ryan Jan 22 '16 at 0:46
• Looks good, that's what I get too. – Daniel Fischer Jan 22 '16 at 0:49