I'm dealing with the following problem in computational programming. I'm trying to find a way to build an algorithm that can quickly resolve the following problem statement without forcing me to do it by hand. Is there any way to group the following relations below by some pattern or identity in order to make finding a possible values of c much more efficiently?

Problem: Given any integer x, where x > 2, is there any integer c, where c > 1 that satisfies one of the following relations for some integer k, where k >= 0.

1. $\frac{x}{11 + 10k} = c \Rightarrow x = 11c + 10ck$
2. $\frac{x}{3 + 10k} = c \Rightarrow x = 3c + 10ck$
3. $\frac{x}{7 + 10k} = c \Rightarrow x = 7c + 10ck$
4. $\frac{x}{9 + 10k} = c \Rightarrow x = 9c + 10ck$

Example $\#1$: $x = 3$ (Does not Satisfy)

From $\#1$: $c = \frac{3}{11 + 10k}$, so for any $k \ge 0$, the denominator will always be larger than $3$. No integer value of $c \gt 1$ will ever satisfy this equation.

From $\#2$: $c = \frac{3}{3 + 10k}$, so for $k = 0$, c would be 1, but the restriction on c is that it must be greater than 1. For $k \ge 1$, the denominator will always be larger than $3$. No integer value of $c \gt 1$ will ever satisfy this equation.

From $\#3$: $c =\frac{3}{7 + 10k}$, so for any $k \ge 0$, the denominator will always be larger than $3$. No integer value of $c \gt 1$ will ever satisfy this equation.

From $\#4$: $c = \frac{3}{9 + 10k}$, so for any $k \ge 0$, the denominator will always be larger than $3$. No integer value of $c \gt 1$ will ever satisfy this equation.

Example $\#2$: $x = 4$ (Does not Satisfy)

From $\#1$: $c = \frac{4}{11 + 10k}$, so for any $k \ge 0$, the denominator will always be larger than $4$. No integer value of $c \gt 1$ will ever satisfy this equation.

From $\#2$: $c = \frac{4}{3 + 10k}$, so for $k = 0$, the denominator does not divide evenly into $4$. For $k \gt 1$, the denominator will always be larger than $4$. No integer value of $c \gt 1$ will ever satisfy this equation.

From $\#3$: $c =\frac{4}{7 + 10k}$, so for any $k \ge 0$, the denominator will always be larger than $4$. No integer value of $c \gt 1$ will ever satisfy this equation.

From $\#4$: $c = \frac4{9 + 10k}$, so for any $k \ge 0$, the denominator will always be larger than $4$. No integer value of $c \gt 1$ will ever satisfy this equation.

Example $\#3$: $x = 37$ (Does not Satisfy)

No integer value of $c \gt 1$ will ever satisfy this equation.

Example $\#4$: $x = 91$ (Satisfies a Relation Above)

From $\#2$: $c =\frac{91}{3 + 10k}$, so for $k = 1$, $c = 7$ will satisfy this equation.

Example $\#5$: $x = 147$ (Satisfies a Relation Above)

From $\#3$: $c =\frac{147}{7 + 10k}$, so for $k = 0$, $c = 21$ will satisfy this equation.

Solution 1:

The $x$'s you're looking for here are composite numbers with an odd prime factor not equal to $5$.

Depending on exactly what you want your algorithm to do, you may or may not have an easy time of it. There is a big difference between knowing that a $c\gt1$ exists and actually finding it. The crux of the problem boils down to knowing what to do with $x$'s that are odd but not divisible by $5$. The existence question is a primality test, which is known to be doable in polynomial time. The finding question requires actual factoring, which is not known to be so easy.

If you don't know what I mean by "primality test" or "polynomial time," I'd be happy to provide some links. Basically "polynomial time" is a formalization of what it means to "quickly resolve" a problem.

(For completeness, if you start with an $x$ that is even and/or divisible by $5$, it's easy enough to factor out all its $2$'s and $5$'s, writing $x=2^m\cdot5^n\cdot x'$. If $x'=1$, you know there is no $c$, while if $x'\gt1$ you can let $c$ be the $2^m\cdot5^n$ part of the factorization.)

Solution 2:

We want to know if $x = c (a + 10k)$ for some integers $c$ and $k$, that is, if $a + 10k$ ever divides $x$. One way to do this is (special case of $a = 3$, the others are similar):

List the divisors of $x$ (this is reasonable for small $x$, it does become a problem if you need to work with rather large values of $x$).

If $x = c d$ for $c > 1$ and $d$ is an integer ending in a three (in base ten), then you can write $d = 3 + 10 k$ for some $k \geq 0$ and $x = c (3 + 10k)$.

The converse is trivial: if $x = c (3 + 10k)$, then $3 + 10k$ is an integer ending in 3 that divides $x$.

Find such an integer and you are done. If there isn't one, this condition cannot be met: 91 is divisible by 13 and 7, 147 is divisible by 3 and 7.

Repeat for the other three conditions (11 will require an integer ending in one, but not equal to one).

I am curious as to if there are any solutions that do not require factoring $x$ first.