CODEWITHSUNDEEP
calgorithmdiscrete-mathematicsnumber-theory
Soumajyoti Sarkar
Soumajyoti Sarkar

Reputation: 593

Modulo operation in output

In most coding competitions where the output of a program is presumed to be very large,it is generally instructed to divide the output by 10000007(or in that case a prime number).What is the significance of the prime number being taken because in many cases I find that the same number is given as 100004(i.e. not a prime number)..?

Upvotes: 4

Views: 531

Answers (1)

Eric Postpischil
Eric Postpischil

Reputation: 224102

A prime number is used for two reasons. One reason is that the integers modulo a prime form a mathematical field. Arithmetic in an field works in many ways like arithmetic on integers. This makes an field useful in certain contest problems where otherwise the sequences used might collapse in some cases. Certain arithmetic might produce zero, other trivial results, or simpler results than desired, because the numbers involve happen upon a factor of the modulus, causing some reduction or elimination to occur.

Another reason is to compel the programmer to deal with arithmetic on integers of a certain size. If a composite number were used, then other techniques could be used that did not resort to arithmetic with large integers.

For example, supposed we want to know what 132 is modulo 35, but we have only a very small processor that cannot handle three-digit numbers, so it cannot compute 132 = 169.

Well, 35 = 5•7, and 13 is congruent to 3 modulo 5 and 6 modulo 7. Instead of computing the square of 13, we can compute the squares of these residues, which tells us that 132 is congruent to 32 = 9 = 4 modulo 5 and is congruent to 62 = 36 = 1 modulo 7. Combining these residues requires some additional knowledge (the Extended Euclidean Algorithm). For these particular numbers, we can multiply the residue of 5 by 21 and the residue of 7 by 15 to get 4·21+1·15 = 99. Reducing that modulo 35 yields 29, which is the answer (the residue of 132 modulo 35).

If the modulus is prime, this circumvention of the arithmetic is not available. A prime modulus essentially requires the use of arithmetic on numbers up to the square of the modulus (or time-consuming workarounds), but a composite modulus would allow the use of arithmetic on smaller numbers, up to just twice the modulus.

Upvotes: 5

Related Questions