How to check 25! is divisible by 9317?
9317= 7x11x11x11 so 25! should contain 3 11’s in it’s prime factorization but it contains only 2 (ie 11,22(=11*2)) so not divisible.
2 Likes
The algorithm is that first prime factorize the divisor(find the powers of all prime factors of the divisor in this case 9317 = 7^1*11^3).This is easy.
Next check if the dividend has all these prime factors. In this case of 25! you can easily find multiples of 11 and check how many are there multiples of 7 and so on.
If the dividend at least has all the prime factors of the divisor then it is divisible else it is not.
Now, the question becomes interesting if you put some arbitrary numbers to check whether a | b!.
To solve this, take a prime p>a.Now, calculate c=b!%p, so that int size does not overflow.Now calculate whether a|c using MMI or Modular Multiplicative Inverse.Hope this generalization was useful.
1 Like
no,25! is not divisible by 9317.
Please design algorithm.
How will you check the divisibility using MMI? I read just now that MMI can be used to find an integer such that the product is 1 modulo some number. How can you extend this to find if there is some number such that product is c?