# Proof of Prime Maker Conjecture

In my mind the following conjecture is true:

Prime Maker Conjecture

I call a number $n$ factor-resistant to $q$ if $q\not\mid n$. Considering $n$ as a composite number, the idea is to make $n$ factor-resistant to all of its (prime) factors. When we multiply a number minus or plus $1$ with one of its (prime) factor and then add or subtract 1, the number would become factor-resistant to that (prime) factor.

The Algorithm:

1. Let $n=m\mp 1$ ($m$ is even).

2. Perform a primility test on $n$, if $n$ is prime output Prime and exit.

3. Find the smallest prime factor $d_0$ of $n$

4. Set $m = d_0 \times m$.

5. Set $n= m \pm 1$

6. Go to Step 2

Example

We choose $m=541\#$ ($\#$ is primorial sign) and positive side.

1. $n=541\#+1$

2. $IsPrime(n)$ ? $n$ is composite

3. $d_0=2879$

4. $m = 2879 \times 541\#$

5. $n= m +1$

6. $IsPrime(n) ? n$ is composite

7. $d_0=342085039$

8. $m=342085039\times 2879 \times 541\#$

9. $n = m + 1$

10. $IsPrime(n) ? n$ is prime.

Of course the most time consuming step in the algorithm is finding the (smallest) factor, sometimes it makes the algorithm impractical but for a math proof we can think of it as a fast operation.

My conjecture is that, the number of required iterations of this algorithm to convert a composite number to prime one, is finite, but I have no idea how to prove it or even approach it ...

Update

I've just made the algorithm more clear.

More Samples

• $n = 1549 \times 57179\times 102932777 \times 67118797 \times 718049 \times 8466769 \times 4261711 \times 1444603 \times 100! + 1$
• $n = 18593 \times 3119\# + 1$ is a 1327 digits prime
• $n = 1732043 \times 142981 \times 97787 \times 376001 \times 7933\# + 1$ is a 3423 digits prime
• In step 4 of the algorithm, do you mean to multiply $m$ by $d_0$? Or did you mean $n$? Mar 2 '13 at 11:29
• And what do you mean by $p_{100}$ in your example? Mar 2 '13 at 11:49
• To multiply $m$ by $d_0$ and put the result $+1$ into $n$. It is primorial of 100th prime. Mar 2 '13 at 14:50
• But $d_0$ is not a prime factor of $m$. So you can't apply the statement about "When we multiply a number with its smallest prime factor and then add or subtract 1..." Mar 2 '13 at 15:13
• $d_0$ is a prime factor of $n$ or $m+1$, so $d_0 \mid m+1$, and so then we have $d_0 \not\mid d_0\times m + 1$. Got it? Mar 2 '13 at 15:47

Your algorithm does not converge as it is described.

Example: $m = 24$. Choose "+1" throughout. Then initially $n = 25$.

1. $n$ is composite
2. $d_0 = 5$
3. $n$ becomes $121$
4. $n$ is composite
5. $d_0 = 11$
6. $n$ becomes $265$
7. $n$ is composite
8. $d_0 = 5$
9. $n$ becomes $121$

and so on.

Your example on the other hand updates the number $m$ in each step. Is that what you have in mind?

• No, he just explained it poorly. See his example - third $n$ should be $11 \times 5 \times 24 + 1$. I did a little testing and found that this way at least first 96 integers work. Mar 3 '13 at 6:03
• @Hans Engler, I've updated the algorithm with correct explaination Mar 3 '13 at 6:59