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

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
CPU Time limit1 second
Memory limit1024 MB
?
DifficultyNot Available
LinksStatistics
DownloadsSample data files
Source & LicenseAtli Fannar FranklínE-402-STFO 2024 Module NCreative Commons License (cc by-sa)