# how to calculate all numbers of the form $6x-1, 6x+1, 6x+5$ that are not divisible by $5,7$ or $11$?

This is purely a hobbist question, I would simply like to know what methods are currently used to find the answer to this question. (Does modular arithmetic suffice in finding all the "$x$" values that when plugged back into all of the 3 functions: $6x-1,6x+1$ and $6x+5$, will give numbers that aren't divisible by 5,7 or 11? And if yes, how so?)

Thank you.

P.S.: I know that there is exactly 64 functions I would need to plug into the "$x$" value to solve this. But I want to know what other methods there are in solving this! :)

• You can look at it as $(6x-1)(6x+1)(6x+5)$ relatively prime to $5\cdot 7\cdot 11=385$. From there, you can brute force it by checking each value $x=0,1,2,\dots,384$. Possibly faster than bruite force is to do a Chinese Remainder Theorem approach. May 5, 2014 at 13:38

$x\equiv 0,1,4\pmod 5$ if and only if $(6x-1)(6x+1)(6x+5)$ is divisible by $5$, so you need $x\equiv 2,3\pmod 5$.

$x\equiv 1,5,6\pmod 7$ if and only if $(6x-1)(6x+1)(6x+5)$ is divisible by $7$, so you need $x\equiv 0,2,3,4\pmod 7$.

$x\equiv 1,2, 9\pmod {11}$ if and only if $(6x-1)(6x+1)(6x+5)$ is divisible by $11$, so you need $x\equiv 0,3,4,5,6,7,8,10\pmod {11}$.

So, modulo $5\cdot 7\cdot 11= 385$, you get $2\cdot 4\cdot 8=64$ possible values of $x$.

You can use Chinese remainder theorem to find these $x$. If $x\equiv a\pmod {5}, x\equiv b\pmod 7$ and $x\equiv c\pmod {11}$, then:

$$x\equiv a\cdot7\cdot 11\cdot 3 + b\cdot 5\cdot 11\cdot (-1) + c\cdot 5\cdot 7\cdot 6\pmod {385}$$

Substutiting, for example, $a=2,b=2,c=0$ gives:$$x\equiv 2\cdot 231 + 2\cdot (-55) + 0\cdot 210=352\pmod{385}$$

So if $x\equiv 352\pmod {385}$, it satisfies your condition.

You can do this for all possible triples $(a,b,c)$ given the constraints noted at the beginning. This gives $64$ possible values, modulo $385$.

You could also just try all values from $x= 0,1,\cdots,384$ and get the possible remainders.

\begin{align}x\equiv & 3, 7, 17, 18, 28, 32, 37, 38, 52, 58, 63, 72, 73, 77, \\ & 87, 88, 93, 98, 102, 107, 128, 137, 142, 143, 147, \\ & 157, 158, 168, 172, 182, 192, 193, 198, 203, 212, \\ & 213, 217, 227, 228, 238, 242, 247, 248, 252, 263,\\ & 268, 282, 283, 297, 303, 308, 312, 318, 322, 333, \\ & 338, 347, 352, 357, 367, 368, 373, 378, 382\pmod {385}\end{align}