ankurrathinsit's blog

Need Help on Modular Arithmetic question
By ankurrathinsit, history, 5 years ago, In English

Suppose we are given number N we have to find a number M less than N such that M*M when divided by N gives maximum remainder . Also value of M should be maximum possible ( nearest to N).

It is given that all computed values are within integer range. for e.g : N=15

maximum remainder is obtained from M=5 and M=10

so M = 10 is the answer.

I could only formulate the naive solution for it which works in O(N) time complexity. Any better approach for this ??

  • Vote: I like it
  • +20
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
5 years ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

First of all it's always useful to post the source of the problem you need help with. It increases the chance of you getting any help, and also to make sure you didn't get it from an on going contest or whatever.

I searched a bit but I couldn't find a full solution that works in better than O(N), but here is what I have so far:

  • Let $$$X = sqrt(N) - 1$$$, now we have $$$X^2$$$ as a candidate. All we need to do know is verify if there exists a better possible modulo than it, which is the range from $$$[X^2; N-1]$$$ which is $$$O(sqrt(N))$$$

  • The problem now is; having $$$N,M$$$ does there exist an integer $$$X$$$ such that $$$X^2 = M (modulo N)$$$ or not

  • This means finding out if $$$M$$$ is a quadratic residue modulo $$$N$$$.

  • This can be found using the quadratic reciprocity which finds this for a prime $$$N$$$, but you can get around that using CRT on the prime factors of $$$N$$$.

  • The last problem is that I read that this is only possible for $$$M$$$ coprime to $$$N$$$, although I didn't find it explicitly mentioned in the wikipedia article, it was in a stackexchange answer.

Maybe someone can shed a light on this?

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Maybe I'm over-complicating it but this is my approach.

Let’s try to find largest $$$x$$$ such that there exists $$$a$$$ which satisfies $$$a^2 \equiv x \mod n$$$ (Also known as a quadratic residue mod n).

Let's iterate from $$$n-1$$$ to $$$0$$$. Check if $$$i$$$ is a quadratic residue by an extension of Euclid’s criterion. You can read about it on wikipedia https://en.wikipedia.org/wiki/Quadratic_residue. If it is then break.

Then after finding x, you can use the algorithm described here to find $$$a$$$ http://www.numbertheory.org/php/squareroot.html

The for loop will go through $$$O(\sqrt{n})$$$ values at most as that will be the gap between squares just below and above $$$n$$$, So that's a worst case upper bound.

→ Reply