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.

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

  • $\begingroup$ 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? $\endgroup$ – Biggiez Nov 26 '17 at 12:39
  • $\begingroup$ $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)$ $\endgroup$ – Peeyush Kushwaha Nov 26 '17 at 12:41
  • $\begingroup$ 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? $\endgroup$ – Biggiez Nov 26 '17 at 12:44
  • $\begingroup$ @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. $\endgroup$ – Peeyush Kushwaha Nov 26 '17 at 12:46
  • $\begingroup$ Yea okay that was what I was wondering about. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.