Enjoying 2018 while it lasts, Part 4
Consider the set S of all positive integers n such that the congruence x ≡ x 2 ( m o d n ) has more than 2018 solutions x with 0 ≤ x < n . In S , let N be the smallest integer such that Ω ( n ) = 2 0 1 8 , where Ω ( n ) denotes the number of prime factors of n , counted with their multiplicities. Find the multiplicity of the prime factor 2 in N .
The answer is 2008.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
Exactly! Thank you, Patrick!
I also breathe a sigh of relief; since there had been no correct answer in two days, I started to worry that something was wrong with the problem.
I missed out something. That is Chinese remainder theorem. It is impossible to solve this without using that. I felt this problem is wrong. Z/nZ is isomorphic to product of groups Z/pi^ki Z. If n=p1^k1 p2^k2 ....pt^kt. I have a doubt if we have n modular equations given n distinct primes day p1,p2,....pn. X=ar mod(pr). Where r=1to n . We can find a solution as the isomorphism gives us a solution. But in this case it is much complex here it is x^2-x. Then how can you say that solution exists.
Log in to reply
Things are not as complex as you fear. In ∏ i = 1 m Z / p i k 1 , the idempotents x , with x 2 = x are simply those elements whose components in their respective Z / p i k 1 are all idempotents. But, as Patrick explains, those are all 0's and 1's. Thus there are 2 m = 2 ω ( n ) idempotents in the product ring, which, as you say, is isomorphic to Z / n .
Log in to reply
Thanks I got it. In this case things are simple. If we have a system of modular equations where we have general quadratic functions. Then life is not so easy.
Log in to reply
@Srikanth Tupurani – Can you give an example of a "not so easy" system? The Chinese Remainder Theorem is pretty powerful.
Log in to reply
@Patrick Corn – Suppose instead of x^2-x we had x^2+5x+1 how you will solve this problem. Much more. Worse situation is when you have nth degree polynomial. May in these cases you need a computer program to solve the problem.
Log in to reply
@Srikanth Tupurani – Yes, that would be a tedious problem; not that interesting. The congruence x 2 ≡ x is of particular interest since we are counting the idempotents; those are useful in many contexts.
Log in to reply
@Otto Bretscher – That is true. Idempotents are interesting. Sir I want to read the book written by you on linear algbera. Is it available online. Sorry I should not ask this question here.
For any prime p and positive integer k , the congruence x 2 ≡ x ( m o d p k ) has exactly two solutions: if p k divides x ( x − 1 ) , exactly one of the factors is divisible by p , so it must be divisible by the full p k , so the only solutions are 0 , 1 . So by the Chinese remainder theorem , the number of solutions to the general congruence x 2 ≡ x ( m o d n ) equals 2 ω ( n ) , where ω ( n ) is the number of distinct prime factors of n . So S is the set of positive integers n with ω ( n ) ≥ 1 1 .
So N has at least 1 1 distinct prime factors, and the sum of the multiplicities of its prime factors is 2 0 1 8 . It's not hard to see that the minimum such N is 2 2 0 0 8 ⋅ 3 ⋅ 5 ⋯ 3 1 , so the answer is 2 0 0 8 .