Reykjavik University

Courses/ E-402-STFO/ STFO24/ Module N: All These Squares Make a Circle/ Problems/ Root of Minus One
Log in
Hide

Problem C
Root of Minus One

Accepted submissions to this problem will be granted a score of 10
Languages en is

You are given a prime p satisfying p=1(mod4) and should find a value r that satisfies 0≤r<p and r2=−1(modp).

Input

The first and only line of input contains a prime p≤1018 satisfying p=1(mod4).

Output

Print a value r satisfying 0≤r<p and r2=−1(modp).

Sample Input 1 Sample Output 1 
73

27
Hide

Please log in to submit a solution to this problem

Log in