3
$\begingroup$

Describe how to find a prime factor of 1742399 using at most 441 integer divisions and one square root.

So far I have only square rooted 1742399 to get 1319.9996. I have also tried to find a prime number that divides 1742399 exactly; I have tried up to 71 but had no luck. Surely there is an easier way that I am missing without trying numerous prime numbers. Any help would be great, thanks.

  • 1
    - you need only to test numbers up to $1319$. - test $2$ for even numbers - test $3$ for multiples of $3$ - the remaining numbers will be $1$ or $5 \bmod 6$2012-08-14
  • 0
    @RaymondManzoni This is undoubtedly what the question had in mind. One can also eliminate multiples of 5 fairly efficiently and reduce the number of divisions by working mod 30.2012-08-14
  • 0
    Note also that in Raymond's scheme the first divisor you encounter will be prime (this is not entirely trivial).2012-08-14
  • 0
    @RaymondManzoni Thanks for your help guys. I understand using 2 to test for even numbers and 3 to test for multiples of 3 but I am confused over where the 5 mod 6 comes from.2012-08-14
  • 0
    a prime number greater than $3$ must be equal to $1$ or $5 \bmod 6$ because a prime (larger than $3$) must be odd i.e. $1,3$ or $5 \bmod 6$. Since $3\bmod 6$ was handled by the case $3$ only remains $1$ and $5$.2012-08-14
  • 0
    Let's try it again this way : you'll have to divide $1742399$ until the remainder becomes $0$. Start by dividing by $2,\ 3,\ 5(=6\cdot 1-1),\ 7(=6\cdot 1+1),\ 11(=6\cdot 2-1),\ 13(=6\cdot 2+1),\cdots\ $ (using $-1=5\pmod{6}$). Is this clearer ?2012-08-14

4 Answers 4