Proving Primality Using Minus 1 Divided By 2

Primenumbers · 2018-06-27 01:25:24

THEORY
Take any odd number, y, count the number of times it takes you to get to zero by minusing 1 and dividing by 2, this equals, z. If this action results in an even number, simply add y. If z is a prime number >(square root of y), then y is prime. Example:

y=23
(23-1)/2 = 11 First go
(11-1)/2 = 5 Second go
(5-1)/2 = 2 Third go
23+2 = 25, (25-1)/2 = 12 Fourth go
23+12 = 35, (35-1)/2 = 17 Fifth go
(17-1)/2 = 8 Sixth go
23+8 = 31, (31-1)/2 = 15 Seventh go
(15-1)/2 = 7 Eighth go
(7-1)/2 = 3 Ninth go
(3-1)/2 = 1 Tenth go
(1-1)/2 = 0 Eleventh go
Therefore z=11
z>(square root 23) AND z is prime THEREFORE 23 is prime.

Also if you don't know if z is prime , you can repeat the process!

PROOF
Take any odd number, y, minus 1 and divide by 2 until you get to zero, adding y as necessary when it results in an even number. The factor on the other hand will operate the same way. You can see that this must be the case if you work backwards. What is the remainder for n for 0/n? That's correct, zero. What have I done to y after that? I've multiplied it by 2 and added 1, so I must do the same to the remainder to get the new remainder. What happens when I add y? Well, you will effectively be adding a multiple of n, so you would end up just misusing them again to get the remainder. Eventually on the last number of goes I will end up with y and the remainder n, for y/n where n is a factor.

If y is a prime number the number of goes, z, will never be greater than (y-1). Proof of this is in the fact that, according to Fermats Little Theorem, if y is prime, 2^(y-1) -1 will be factorable by y. So y will always be a factor of 2^(y-1) -1 making z=y-1 or smaller, having occurred beforehand in a smaller z.

Therefore if z= a prime >(square root of y) no potential factor, ( primes below the square root of y) can possibly have the same z because they can't be that big.

Bob · 2018-06-30 04:58:06

hi Primenumbers

That's very interesting. I confess I'm still struggling to follow your proof. I thought I'd collect some evidence to help with this so I wrote a program to do all the sums.

Every number the program said was a prime was indeed a prime. But some known primes weren't detected. Now admittedly you don't claim the algorithm will find all primes but you did say "Also if you don't know if z is prime , you can repeat the process!"

So let's say I try 23 like you but I don't know if z = 11 is a prime.

z=1 (11-1)/2 = 5
z=2 (5-1)/2 = 2
z=3 (2+11-1)/2 = 6
z=4 (6+11-1)/2 = 8
z=5 (8+11-1)/2 = 9
z=6 (9-1)/2 = 4
z=7 (4+11-1)/2 = 7
z=8 (7-1)/2 = 3
z=9 (3-1)/2 = 1
z=10 (1-1)/2 = 0

z is not prime so we cannot determine y = 11

Please would you expand a little on your proof.

Bob

Primenumbers · 2018-06-30 06:29:22

Thanks Bob

Yes you are right. 11 has z=10 which is not prime although is above (square root 11), so we could try using the method again, but we can't because 10 is even. So we can't determine if 11 is prime, and in turn 23 using this method. But if we know 11 is prime and above square root 23, we know 23 is prime, using this method.

The method does not prove that all primes are prime. You seem to have the method down, so I'll expand a little on the proof.

I forgot to mention that for mersenne Numbers, 2^p -1, z=p as you can see below;

2^11 -1
2^10 -1 First go
2^9 -1 Second go
2^8 -1 Third go
2^7 -1 Fourth go
2^6 -1 Fifth go
2^5 -1 Sixth go
2^4 -1 Seventh go
2^3 -1 Eighth go
2^2 -1 Ninth go
2-1 Tenth go
1-1=0 Eleventh go

So, as 2^10 -1 is factorable by 11 according to Fermats Little Theorem, I know that the z for 11 must be 10 or smaller. So as z's can never be bigger than their corresponding y's, if z is bigger than the square root I know that that exact number did not occur in any potential Factors below square root y. And if y has no factors below it's square root, I know it's prime. HOWEVER, if z is a multiple, y could be a factor of something with a smaller z. If you can imagine z being prime and when you get to z goes you turn it into zero and then it takes 2z goes to get to zero again, then 3z, 4z, 5z etc.
Example:

7 is a factor of 49
49 takes 21 goes to get to zero
7 takes 3 goes to get to zero
49's z= a multiple of 3
Therefore 49 has the potential to be factorable by other y's with z=3
7 has z=3, 7 has the potential to be a factor of 49

(0x2) +1=1 First go
(1x2) +1=3 Second go
(3x2) +1=7 Third go
7-7=0 Process starts again
(0x2) +1=1 Fourth go
(1x2) +1=3 Fifth go
(3x2)+1=7 Sixth go
7-7=0 Process starts again
(0x2) +1=1 Seventh go
.................
(3x2) +1=7 Twenty first go

They are only ever potential factors, which is why 11 can have z=10, which has the potential to be factorable by z=2 or z=5, the factors of 10.

Hope this helps......?

(I must admit I'm not very good at explaining things.)

Last edited by Primenumbers (2018-06-30 06:38:20)

Primenumbers · 2018-07-22 05:47:43

If z= a factor of (y-1), we know that 2^(y-1) -1 is factorable by y, as the process starts again for a multiple as seen above. So y is either a prime or a Fermat pseudoprime, which according to Wikipedia are rather rare.

Another way is to take any odd number, y, you want to know if it's prime. So count the number of times it takes you to get to zero by minusing 1 and dividing by 2, adding y if even, this number of times =z. If z= a factor of (y-1) then y is either a prime or a Fermat pseudoprime. Otherwise it is composite.

Primenumbers · 2018-07-31 10:22:56

If z is the smallest Mersenne number that an odd number, y, will be a factor of.

Does anyone know what “z” a composite can’t be?

Math Is Fun Forum

#1 2018-06-27 01:25:24

Proving Primality Using Minus 1 Divided By 2

#2 2018-06-30 04:58:06

Re: Proving Primality Using Minus 1 Divided By 2

#3 2018-06-30 06:29:22

Re: Proving Primality Using Minus 1 Divided By 2

#4 2018-07-22 05:47:43

Re: Proving Primality Using Minus 1 Divided By 2

#5 2018-07-31 10:22:56

Re: Proving Primality Using Minus 1 Divided By 2

Board footer