# Quadratic Residues

Let $$n$$ be a positive integer and let $$a$$ be an integer such that $$gcd(a, n) = 1$$.

$$a$$ is said to be a quadratic residue modulo $$n$$ if and only if there exists a $$x$$ such that: $$x² \equiv a (mod n)$$

When $$n$$ is a prime number $$(n = p)$$ there exist three cases:

1. either $$a$$ is a multiple of $$p$$, or
2. $$a$$ is a quadratic residue, or
3. $$a$$ is not a quadratic residue.

The **Legendre** symbol $$(\frac{a}{p})$$ captures this as follows.

<figure><img src="https://3450804385-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FRIg06sTkCh60KyuJiT39%2Fuploads%2Feh7LE8vCDbOmMcatBQyr%2F2024-01-08_23-35.png?alt=media&#x26;token=236278c0-2e99-40a4-8f58-1d4d9f52c053" alt=""><figcaption></figcaption></figure>

## Legendre Symbol

<figure><img src="https://3450804385-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FRIg06sTkCh60KyuJiT39%2Fuploads%2FW0axrFUqyUaYPAM4LQiS%2F2024-01-08_23-37.png?alt=media&#x26;token=4699f7d2-ccca-4f91-b095-f90d427c665a" alt=""><figcaption></figcaption></figure>

<figure><img src="https://3450804385-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FRIg06sTkCh60KyuJiT39%2Fuploads%2FYSiXEFnvAm0m8Dtb6Vxd%2F2024-01-08_23-38.png?alt=media&#x26;token=ba9f94c8-6c13-4c41-8895-a3aeb01a4ac9" alt=""><figcaption></figcaption></figure>

## Jacobi Symbol

<figure><img src="https://3450804385-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FRIg06sTkCh60KyuJiT39%2Fuploads%2F02k7u8apxYwa0ENiR1lt%2F2024-01-08_23-39.png?alt=media&#x26;token=fc24dfc1-e649-441d-86be-a5d2ec09923c" alt=""><figcaption></figcaption></figure>

## Counts

For a prime $$p$$, the number of integers belonging to the set $$[1, 2, . . . , p − 1]$$ that are quadratic residues is exactly $$(p − 1)/2$$.

```
a(n)=local(v,s);v=vector(eulerphi(n));s=0;\
for(k=1,n,if(gcd(k,n)==1,s=s+1;v[s]=k;););return(v);
qr(n)=local(v);v=a(n); /* number (#) of true quadratic residues */\
return(length(Set(vector(length(v),k,(v[k]^2)%n))));
j(n)=local(v,c);v=a(n); /* # of true or fake quadratic residues */\
return(sum(k=1,length(v),kronecker(v[k],n)==1));
f(n)=return([eulerphi(n),qr(n),j(n)]);
f(101) /* returns [100,50,50] */
f(103) /* returns [102,51,51] */
f(107) /* returns [106,53,53] */
f(109) /* returns [108,54,54] */
```

How about composite numbers that are the product of two distinct prime numbers?

```
f(13*17) /* returns [192,48,96] --- half are fakes! */
f(11*13) /* returns [120,30,60] --- half are fakes! */
f(11*19) /* returns [180,45,90] --- half are fakes! */
```

## Square Roots

<figure><img src="https://3450804385-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FRIg06sTkCh60KyuJiT39%2Fuploads%2Fww7ABBgriqFZTQCCyPwg%2F2024-01-08_23-41.png?alt=media&#x26;token=ebd27dac-2582-4bbf-82a0-8d6bf66f0238" alt=""><figcaption></figcaption></figure>

Example:

```
p=11; q=19; n=p*q; r=20; a=lift(Mod(r^2,n));
rp=lift(Mod(a,p)^((p+1)/4)); rq=lift(Mod(a,q)^((q+1)/4));
r1=lift(chinese(Mod( rp,p),Mod( rq,q))); /* 20, (r1/p)=+1, (r1/q)=+1 */
r2=lift(chinese(Mod( rp,p),Mod(-rq,q))); /* 75, (r2/p)=+1, (r2/q)=-1 */
r3=lift(chinese(Mod(-rp,p),Mod( rq,q))); /* 134, (r3/p)=-1, (r3/q)=+1 */
r4=lift(chinese(Mod(-rp,p),Mod(-rq,q))); /* 189, (r4/p)=-1, (r4/q)=-1 */
```

### Factorization

<figure><img src="https://3450804385-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FRIg06sTkCh60KyuJiT39%2Fuploads%2FqCg8AN0TXATAhXaBKPn1%2F2024-01-08_23-42.png?alt=media&#x26;token=a8318e30-e9af-45fd-86ae-78be6bf6a551" alt=""><figcaption></figcaption></figure>

Example (continuation of the code of the previous slide):

```
p=11; q=19; n=p*q;
r1=20; r2=75; r3=134; r4=189; /* square roots of 191 */
gcd(r1-r2,n);                 /* 11 */
gcd(r1+r2,n);                 /* 19 */
```

**pari-gp** can only compute square roots when the modulus is prime:

```
sqrt(Mod(5,11))    /* ok (because 5 is a quadratic residue)     */
sqrt(Mod(9,14))    /* error (because the modulus is not prime)  */
```
