Quadratic reciprocity tells us that

which is just terrible: the parentheses are different sizes, on the Legendre symbol on the left p and 3 are closer together and on the right further apart. Normally this doesn’t come up because you rarely have two nearly identical fractions side by side and enclosed by parentheses, but when talking about quadratic residues it’s quite common. One solution is to change the \left and \right tags to \bigg

It looks good enough, but if you’re going to the trouble, you might as well define a command to do it for you. I copied one from the LaTeX stackexchange and modified it with the fix above

\makeatletter
\def\legendre@dash#1#2{\hb@xt@#1{%
\kern-#2\p@
\vrule\@height.2\p@\@depth.2\p@\@width\p@
\kern.5\p@}\hfil
\kern-#2\p@
}}
\def\@legendre#1#2#3#4#5{\mathopen{}\bigg(
\sbox\z@{$\genfrac{}{}{0pt}{#1}{#3#4}{#3#5}$}%
\dimen@=\wd\z@
\kern-\p@\vcenter{\box0}\kern-\dimen@\vcenter{\legendre@dash\dimen@{#2}}\kern-\p@
\bigg)\mathclose{}}
\newcommand\legendre[2]{\mathchoice
{\@legendre{0}{1}{}{#1}{#2}}
{\@legendre{1}{.5}{\vphantom{1}}{#1}{#2}}
{\@legendre{2}{0}{\vphantom{1}}{#1}{#2}}
{\@legendre{3}{0}{\vphantom{1}}{#1}{#2}}
}
\def\dlegendre{\@legendre{0}{1}{}}
\def\tlegendre{\@legendre{1}{0.5}{\vphantom{1}}}
\makeatother


It looks like this

\legendre{p}{3}\legendre{3}{p}=(-1)^{(p-1)/2}

Which is nice, since it isn’t identical to a fraction. It doesn’t, however, fix the issue with the spacing. I think that’s because the bounding box of the p in this font has some whitespace on top and 3 has on the bottom. But you can just fix that by changing the font.