1
$\begingroup$

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.

$\endgroup$
0

2 Answers 2

2
$\begingroup$

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

$\endgroup$
8
  • $\begingroup$ Okay, I see...so I have implemented a solution to actually verify a number's primality (so it finds c > 1 if it exists), but it's not an existence test, so its not in polynomial time: stackoverflow.com/questions/15743192/… $\endgroup$
    – Alexandru
    Jun 23, 2014 at 14:53
  • 1
    $\begingroup$ This is equivalent to my answer, but much cleaner. $\endgroup$
    – Zach
    Jun 23, 2014 at 15:43
  • $\begingroup$ Barry, what polynomial-time primality test would you recommend? From what I've read online, a polynomial time solution would be the AKS primality test (en.wikipedia.org/wiki/AKS_primality_test) or the Miller-Rabin primality test (en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test)... $\endgroup$
    – Alexandru
    Jun 23, 2014 at 17:51
  • $\begingroup$ Barry, is it not true that for a number to be prime, it must not be divisible by another prime number below its square root? That would make factoring easier if you had a cache of primes. $\endgroup$
    – Alexandru
    Jun 25, 2014 at 17:56
  • $\begingroup$ @Alexandru, trial division by primes up to the square root rapidly becomes too time-consuming to be practical for numbers with a large number of digits. If you're working in a programming language that has a built-in factoring or primality-test algorithm, use it. If you have to write your own, you need to carefully consider how large the numbers are that you expect (or need) to deal with. $\endgroup$ Jun 25, 2014 at 19:00
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ See the answer by Barry for a simpler way to check the same thing. $\endgroup$
    – Zach
    Jun 23, 2014 at 15:44

You must log in to answer this question.

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