Modulus PHP Problem

Question

I have a problem, I am trying to calculate what the lowest prime is of a number but I do not understand the result that PHP is giving me.

If I have this number

 $number = 600851475143;

Then I modulus it:

$primes = array( 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97);

    foreach($primes as $key=>$value) {    
        if($number % $value == 0 ) {echo $value; break; }
    }

Why is it that $value = 3? If $value = 3, that means that 600851475143 / 3 should be an integer, but its not. So I do not understand why that if() evaluates to true?

Answer 1

I might be misunderstanding it, but modulo gives you the rest of a division, so e.g. 600851475143 / 3 is 200283825047 rest 2 and this is what it gives you back.

Answer 2

Using PHP 5.2.8, it fails as described in the question. It seems like the modulo operator doesn't work on big integers. You should consider using bc_mod (modulus with arbitrary precision):

<?php

$number = 600851475143;

$primes = array(2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97);

    foreach($primes as $key=>$value)
    {    
        if($number % $value == 0 ) {echo $value."<br/>"; }
        if(bcmod($number, $value) == 0) {echo "bcmod ".$value."<br/>"; }
    }

?>

The above code prints:

3

29

bcmod 71

Answer 3

See this bug listing here

% does not not work for numbers over 2^31 (32-bit) or 2^63 (64-bit). Use BCMOD instead.