Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Divisibility Testing

  1. Dec 15, 2003 #1
    We've seen divisibility testing for different numbers...for 2,3,4,5,7,11.......

    But now I want to know is there any way to find divisbility with any prime number?

    Suppose, how can I say 12783461236 is divisible with 97 or not?
  2. jcsd
  3. Dec 15, 2003 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Yes, there exist divisibility tests of that type for any number (not just primes), but in general they probably take more effort to use than simply dividing it by hand. The divisibility by 7 test hints at the way things get complicated...
  4. Dec 15, 2003 #3


    User Avatar
    Science Advisor
    Homework Helper

    Take the last digit, multiply by 29, subtract from the rest, and see if the result is divisible by 97?

    It's probably faster to just trial divide.
  5. Dec 16, 2003 #4
    Actually I want to build a computer program...which can take any arbitrary size of 2 integers can tell larger one is divisible by the smaller one!

    Can you give any link to proceed on???
  6. Dec 16, 2003 #5


    User Avatar
    Science Advisor
    Homework Helper

    Arbitrary precision arithmetic is pretty straightforward.

    Google on it for more information.
  7. Dec 16, 2003 #6
    Yes! I know, but I am going to develop a program myself :)

    The google results I've got so far are with traditional division method, there is no use of such type of divisibility testing....

    I want to develop one with this feature, then it will be faster than others available with stright forward DIVISION !!!
  8. Dec 16, 2003 #7


    User Avatar
    Science Advisor
    Homework Helper

    Observation 1:

    The number of operations that you need for a 'traditional' division approach is [tex]log_2 m * log_2 n[/tex] where [tex]m,n[/tex] are the numbers that you're using. That's really fast already. So fast that checking numbers with thousands of digits should not take very long.

    Are you trying to do some sort of crypto stuff?
  9. Dec 17, 2003 #8
    I just want to program myself with the use of Divisibility testing...

    For traditional division I use:

    It's not that crypto tech...just making math soft and learning algorithms :)
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook