Search code examples
javabigintegerbigintfactorization

Java BigInteger factorization: division and multiplication differ

I'm writing a code to factorize a big number (more than 30 digit) in Java.

The number (n) is this: 8705702225074732811211966512111

The code seems to work and the results are:

  • 7
  • 2777
  • 14742873817

By logic the last item should be obtainable by doing (n/(fact1 * fact2 * fact3)) and it results:

  • 30377199961175839

I was very happy with this, but then decided to take a little test: I multiplied all the factor expecting to find n... But I didn't!

Here is my check code:

BigInteger n = new BigInteger("8705702225074732811211966512111");

BigInteger temp1 = new BigInteger("7");
BigInteger temp2 = new BigInteger("2777");
BigInteger temp3 = new BigInteger("14742873817");
BigInteger temp4 = n.divide(temp1).divide(temp2).divide(temp3);

System.out.println(n.mod(temp1));
System.out.println(n.mod(temp2));
System.out.println(n.mod(temp3));
System.out.println(n.mod(temp4));

System.out.println(n.divide(temp1).divide(temp2).divide(temp3).divide(temp4));
System.out.println(temp1.multiply(temp2).multiply(temp3).multiply(temp4));

System.out.println(n);

As you can see I simply define the number n and the factors (the last one is defined as n/(fact1 * fact2 * fact3) then check that n/eachfactor gives remainder 0.

Then I check that ((((N / (fact1)) / fact2) / fact3) / fact4) = 1

Lastly I check that fact1 * fact2 * fact3 * fact4 = n

The problems are:

  1. n mod temp4 is not 0, but 245645763538854
  2. fact1 * fact2 * fact3 * fact4 is different from n
  3. but ((((N / fact1) / fact2) / fact3) / fact4) = 1

Here is the exact output:

0
0
0
245645763538854
1
8705702225074732565566202973257
8705702225074732811211966512111

This has no sense... How can the fourth factor be wrong and right at the same time?

Solution 
  • System.out.println(temp3.mod(temp1));

    The above code gives 0, which means temp3 is not prime. temp4 is not a factor.