# Problem with simplification of Legendre symbol

Could anyone explain why this is true:

If $p$ is an odd prime and $a'$ is defined by $aa'\equiv 1 \, \text{(mod p)}$ then $(a(a+1)/p)=((1+a')/p)$

Doesn't this by the properties of Legendre symbol mean that $a(a+1) \equiv 1+a' \, \text{(mod p)}$ ? I cant see how this is true. I guess it follows from the fact that $aa'\equiv 1 \, \text{(mod p)}$, but cant really make the connection.

• Are your things which you are using a forward slash to denote Legendre symbols? – Matt Nov 26 '17 at 12:18
• Note that $a'$ is a square iff $a$ is. So replace $a(a+1)$ with $a'(a+1)$. – lulu Nov 26 '17 at 12:19
• @MattS Yes $(a/b)$ denotes the Legendre symbol. – Biggiez Nov 26 '17 at 12:19
• @lulu I didn't really understand what you meant with "$a'$ is a square iff $a$ is" ? – Biggiez Nov 26 '17 at 12:22
• What don't you understand? If $a\equiv x^2$ then $a'\equiv (x')^2$. – lulu Nov 26 '17 at 12:23

Doesn't this by the properties of Legendre symbol mean that $a(a+1) \equiv 1+a' \, \text{(mod p)}$

No, it does not. The property of the Legendre symbol which you're referring to only works in one direction, i.e. $a \equiv b \mod p \implies (a/p) = (b/p)$. If it worked in the opposite direction it would mean all quadratic residues are $\equiv$ mod p, e.g. $1 \equiv 4 \mod 7$, clearly not true.

With this misconception out of the way, consider the proof of $$aa'\equiv 1 \, \text{(mod p)} \implies (a(a+1)/p)=((1+a')/p)$$

First we prove a Lemma that $(a/p) = (a'/p)$.

Case 1: $(a / p) = 1 \implies r^2 \equiv a \mod p$ for some $r$. $r$ has an inverse mod p (since p is prime), call it $r'$. Multiplying both sides by $r'$ $$r^2 r'^2 \equiv a r'^2 \mod p$$ $$\implies 1 \equiv a r'^2 \mod p$$ but since a has a unique inverse mod p, that means $$r'^2 \equiv a' \mod p$$ and so $(a'/p) = 1$

Case 2: $(a/p) = -1$ Suppose BWOC that $(a'/p) \neq -1$ then $(a'/p) = 1$ which means from the previous case that $(a/p) = 1$, a contradiction. So $(a/p) = -1$

P.S. There is no case $(a/p) = 0$ because then $a = 0$ which has no multiplicative inverse.

We know that $(a/p) = (a'/p)$, so

$$(a(a+1)/p)=(a/p)((1+a)/p)$$$$= (a'/p)((1+a)/p)$$$$= (a'(1+a)/p)$$$$= ((a'+1)/p)$$

• How do we know that $(a/p)=(a'/p)$ ? And when you break out $(a(a+1)/p)$ into $(a/p)((1+a)/p)$ dont we need to assume that $1+a$ also is relatively prime to $p$? How do we know this? – Biggiez Nov 26 '17 at 12:39
• $1 + a$ and $a$ are always relatively prime. If they had a common divisor $k > 1$ then $k \mid (a + 1) - a \implies k \mid 1$, a contradiction. I'll update my answer to include a proof for $(a/p) = (a'/p)$ – Peeyush Kushwaha Nov 26 '17 at 12:41
• Ah okay, but what I meant was that if $a+1$ is also relatively prime to $p$ ? Isn't that one of the requirements when one splits up $(ab/p)=(a/p)(b/p)$? That both $a$ and $b$ has to be respectively relatively prime to $p$? We know $a$ is relatively prime to $p$ since it has a multiplicative inverse mod p. But is this true for $a+1$ also? – Biggiez Nov 26 '17 at 12:44
• @Biggiez that's really silly. If one of $a$ or $b$ wasn't relatively prime to $p$ already that would mean it is 0, so your LHS is now 0 and so is your RHS. – Peeyush Kushwaha Nov 26 '17 at 12:46
• Yea okay that was what I was wondering about. – Biggiez Nov 26 '17 at 12:47

We have $aa'=1+jp$, now assume that $(a(a+1)/p)=1$ then there is $x$ such that \begin{eqnarray*} a(a+1)=x^2+kp \\ \end{eqnarray*} Multiply by $a'^2$ \begin{eqnarray*} aa'(aa'+a')=(xa')^2+kpa'^2 \\ (1+jp)(a'+1+jp)= a'+1+jp(a'+2)+j^2p^2=(xa')^2+kpa'^2 \\ a'+1=(xa')^2+p(ka'^2-j(a'+2)-j^2p) \\ \end{eqnarray*} So $((1+a')/p)=1$. There are the two other cases to consider.