2
$\begingroup$

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! :)

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Thomas Andrews
    May 5, 2014 at 13:38

1 Answer 1

Reset to default
5
$\begingroup$

$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.

The complete answer is:

$$\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}$$

$\endgroup$
2
  • $\begingroup$ (Had the wrong value set for 11. Fixed.) $\endgroup$
    – Thomas Andrews
    May 5, 2014 at 14:52
  • $\begingroup$ Thank you for your answer Thomas Andrews! That was very helpful! I actually found a different way of getting those 64 values exactly. I still don't know how it actually works but I'm amazed it worked. Now I need to figure out how its all related. Thanks! $\endgroup$
    – 7uc
    May 27, 2014 at 0:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .