Question

I am given 3 values lets say A, B and P,and I have to find the number of roots of the equation
x^3 = 1 mod P in the interval [A,B], endpoints inclusive.

Answer 1

Like for
1 100 2 answer would be 50.....
1 100 31 answer would be 11...etc..
can anyone explain how to do this mathematically?

Answer 2

@ganeshie8 @hartnn

Answer 3

1 mod P will always return 1*sign(P), so I don't see how that's any helpful.

Answer 4

so how do we get 50 in first case?

Answer 5

Is P guaranteed to be prime?
using the letter P is suggestive

Answer 6

nope its not

Answer 7

http://prntscr.com/4v2451

Answer 8

(p) means mod p

Answer 9

Let's worry about the quadratic equation later
focus on x - 1 = 0 (p) first

Answer 10

http://prntscr.com/4v24ft

Answer 11

Just quadratics are harder to handle with modular arithmetic. I'm trying to avoid setting this equal to n * p and trying to solve for x

Thinking... hmm

Answer 12

Also trying to avoid the chinese remainder theorem.
Just thinking... this is a bit tough :o

Answer 13

http://prntscr.com/4v270e

Answer 14

http://prntscr.com/4v2741
now, checking when the modulos are equal

Answer 15

http://prntscr.com/4v277y

Answer 16

where is the poor 50?

Answer 17

just thinking if there's an easy way to handle this then similar algebra as before

Answer 18

nah don't see it
so...

Answer 19

oh lol... we'll get there

Answer 20

lets do something simple.....xD

Answer 21

http://prntscr.com/4v27lw

Answer 22

just putting it all together

Answer 23

http://prntscr.com/4v28wx

Answer 24

Ug, now I'm getting confused on what floor and ceiling are moment
greatest integer less than or equal to 99/2 is 49
yes, least integer greater than or equal to 10101/2 is 5051
okee...

Answer 25

yep....

Answer 26

http://prntscr.com/4v294s

Answer 27

why did we get an over estimate
Let me see...

Answer 28

http://prntscr.com/4v2d1e

Answer 29

So what have found here above here, actually. ^ I've solved for when x^2+x+1 is congruent to zero mod p. So this means x^2+x+1 is a multiple of p. Using the quadratic formula, we are able to pin point x values that work. But this clearly will give non-integer solutions. But we only consider intege
r x values. So when we get this number range for n 1 <= n <= 5050. n can only take on certain values here in this range, so we're way over counting
because only for certain n will x be integer

In the linear case when we are solving x - 1 congruent to zero mod p, we don't have this problem because for any integer n, x is automatically an integer too
so we can count simply there
So the question shifts to how do we count the number of integer solutions in the quadratic case or will the quadratic residue actually yield any unique solutions not already accounted for by the linear residue x-1 congruent to 0 mod p
I believe the answer is no, but to see why hmm

Answer 30

ohhh i see

Answer 31

tag someone who knows this topic :(

Answer 32

Hmm... just trying to see if (x-1) is a factor of x^2+x+1 mod 2

Answer 33

use euclidean algorithm

Answer 34

its not :(
http://prntscr.com/4v2ezx

Answer 35

Sorry rusty with euclidean algorithm. So we can't escape the situation by claiming that all the roots of x-1 are also roots of x^2+x+1 this way

Answer 36

Okay so then what happens when we solution x -1 congruent to x^2+x+1
Thinking.. need to discount non-integer solutions or do we just need to modulo by 100

Answer 37

---> http://prntscr.com/4v2lps
In all the test cases I tried so far this formula actually works
But I can't come up with the reason at the moment to ignore the quadratic residue part yet, I'll think about it :)

Answer 38

alright!

Answer 39

still looking for a solution ?

Answer 40

Yes man. :)

Answer 41

\(\large x^3 \equiv 1\pmod P\)
\(\large (x-1)(x^2+x+1) \equiv 0 \pmod P\)
\(\large (x-1)(y^2+3) \equiv 0 \pmod P\)

we define :
\(\large y = 2x+1\)

Clearly \(\large x\equiv 1 \pmod P\) is a solution
lets see how many solutions the other factor \(\large y^2+3\equiv 0\pmod P\) gives

Answer 42

say \(\large P = p_1^{e_1}p_2^{e_2}\ldots p_r^{e_r}\)

we can show that the congruence \(\large x^2\equiv a\pmod{ p_i^{e_i}}\) has a solution if and only if the congruence \(\large x^2 \equiv a \pmod {p_i} \) has a solution. So the problem reduces to finding number of solutions in `distinct primes` : \(p_1, p_2, \ldots , p_r\)

\[\large y^2+3\equiv 0 \pmod{p_i} \]

Answer 43

we are almost done - assuming \(p_i\)'s are odd and appealing to Euler's criteriosn, above congruence will have exactly TWO solutions only when \(\large (-3)^{(p_i-1)/2}\equiv 1 \pmod{p_i}\)

Answer 44

http://en.wikipedia.org/wiki/Euler's_criterion

Answer 45

Example : \(\large x^3 = 1\pmod{31}\)
\(\large\color{red}{ x\equiv 1 \pmod {31}}\) is one solution,
For other solutions, we need to solve : \(\large y^2 +3\equiv 0\pmod{31}\)
since \(\large (-3)^{(31-1)/2}\equiv (-3)^{15} \equiv 1 \pmod{31} \), this will have exactly two solutions : \(\large 11, 20\)

solving \(\large 2x+1\equiv 11 \pmod {31}\) and \(\large 2x+1 = 20 \pmod {31}\) you get : \(\large \color{red}{x\equiv 5 \pmod{31}} \) and \(\large \color{red}{x\equiv 25 \pmod{31}} \) as other solutions

Answer 46

you can count the number of solutions :

1 <= 31k+1 <= 100
1 <= 31k+5 <= 100
1 <= 31k+25 <= 100

you will get 4+4+3 = 11 solutions in interval [1, 100]

Answer 47

lets do one more example ?

Answer 48

how about no :P

Answer 49

i didnt know this was so hard ;\

Answer 50

its not hard if you just want to know the `number of solutions` in mod P

Answer 51

it is hard if you want to know number of solutions in a given range because you need to know the actual solutions to find that count

Answer 52

btw, all these are standard methods.. nothing new.. google solving quadratic congruences or quadratic reciprocity law..

Answer 53

alright ill read a bit about this :o

Answer 54

..