You are not logged in. Please login at www.codechef.com to post your questions!

×

Check 25! is divisible by 9317?

How to check 25! is divisible by 9317?

asked 27 Nov '16, 23:24

shahadatcs's gravatar image

0★shahadatcs
5315
accept rate: 0%


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.

link

answered 27 Nov '16, 23:35

diveshuttam's gravatar image

3★diveshuttam
53718
accept rate: 27%

Please design algorithm.

(29 Nov '16, 21:27) shahadatcs0★

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.

link

answered 29 Nov '16, 21:32

sdssudhu's gravatar image

6★sdssudhu
1.1k310
accept rate: 15%

edited 29 Nov '16, 21:39

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.

link

answered 29 Nov '16, 23:39

rajarshi_basu's gravatar image

6★rajarshi_basu
6177
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★

no,25! is not divisible by 9317.

link

answered 30 Nov '16, 00:01

ajay_yadav's gravatar image

0★ajay_yadav
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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