×

# Check 25! is divisible by 9317?

 0 How to check 25! is divisible by 9317? asked 27 Nov '16, 23:24 53●1●5 accept rate: 0%

 4 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. answered 27 Nov '16, 23:35 537●1●8 accept rate: 27% Please design algorithm. (29 Nov '16, 21:27)
 0 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. answered 29 Nov '16, 21:32 6★sdssudhu 1.1k●3●10 accept rate: 15%
 2 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. answered 29 Nov '16, 23:39 617●7 accept rate: 10% 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? (30 Nov '16, 00:04) xrisk3★
 0 no,25! is not divisible by 9317. answered 30 Nov '16, 00:01 1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×1,179

question asked: 27 Nov '16, 23:24

question was seen: 703 times

last updated: 30 Nov '16, 00:04