Show for any odd prime $$p\geq 5,$$ $$\left ( \frac{-3}{p} \right ) =\begin{cases} 1 &amp; \text{ if } p\equiv 1,-5\pmod{12} \\  -1&amp; \text{ if } p\equiv -1,5\pmod{12} \end{cases}$$ So far I have that (1) Let $$p\equiv 1\pmod{4}$$ then $$p\equiv 1\pmod{3}$$ to get $$\left ( \frac{-3}{p} \right )=-\left ( \frac{p}{3} \right )=-\left ( \frac{1}{3} \right )=-1$$ (2)Let $$p\equiv 1\pmod{4}$$ then $$p\equiv 2\pmod{3}$$ to get $$\left ( \frac{-3}{p} \right )=-\left ( \frac{p}{3} \right )=-\left ( \frac{2}{3} \right )=1$$ (3)Let $$p\equiv 3\pmod{4}$$ then $$p\equiv 1\pmod{3}$$ to get $$\left ( \frac{-3}{p} \right )=\left ( \frac{p}{3} \right )=\left ( \frac{1}{3} \right )=1$$ (4)Let $$p\equiv 3\pmod{4}$$ then $$p\equiv 2\pmod{3}$$ to get $$\left ( \frac{-3}{p} \right )=\left ( \frac{p}{3} \right )=\left ( \frac{2}{3} \right )=-1$$ After solving CRT systems I get, $$\left ( \frac{-3}{p} \right ) =\begin{cases} 1 &amp; \text{ if } p\equiv 5,-5\pmod{12} \\  -1&amp; \text{ if } p\equiv 1,-1\pmod{12} \end{cases}.$$ So I'm not sure where I'm messing up. Any help would be appreciated.
45811
Going over a past exam in my elementary number theory course, I noticed this question that caught my attention. The question asked for the conditions that allowed $-3$ to be a quadratic residue mod $p$. Doing some experimentation, I found that this was possible when $p \equiv 1 \pmod 3$. So I guess I have answered part of the question. But the proof is obviously nagging me: Prove $-3$ is a quadratic residue in $\Bbb Z_p$ if and only if $p \equiv 1\pmod 3$. I've done a bit of work on this, but haven't been able to come up with anything close to elegant nor conclusive. Any help would be appreciated.
52019
After some trials, I found out that a prime $p \gt 5$ is congruent to $q\pmod{30}$, where $q$ is also a prime, and $1 \le q \lt 30 \;$ (i.e.  $p \equiv q\pmod{30}.$  Is there a way to write a formal proof to show this?  Is that an acceptable answer.
40670
$(\frac 3p)$ is the Legendre symbol here, not a fraction, if that wasn't clear.  This is what I have so far:  We know by Gauss's Lemma that $(\frac qp) = (-1)^v$ where $$v = \#\left\{1 \le a \le \frac{p-1}{2} \mid aq \equiv k_a \pmod{12}),\space -p/2 &lt; k_a &lt; 0\right\}$$  And we also know that multiples of $(\dfrac{p-1}{2}) \times 3$ must be between $0$ and $p/2$, between $p/2$ and $p$, or between $p$ and $3p/2$.   Representing $p$ as $12k + r$ seems like the next step, but I'm not sure where to go from there.
36548
Show that if $p$ is an odd prime coprime to $7$, then $\left( \frac{7}{p} \right) = 1$ if and only if $p \equiv \pm 1, \pm 3,$ or $\pm 9 \pmod{28}$. HINT: If $p$ is an odd prime, determine which values can $p$ take $\mod28$, and consider each of these values in turn. Note that if we know $p \mod 28$ then we know  $p \mod 4$, and hence we know whether $\frac{p-1}{2}$ is odd or even.   Here, $\left( \frac{a}{b} \right)$ is the Legendre symbol.   The bit I don't understand in the hint is, what do they mean by consider the values that $p$ can take $\mod 28$. Do they mean the values that would make $p$ a quadratic residue $\mod 28$, i.e all the $x$ values satisfying $x^2 \equiv \mod 28$, because then isn't this just $1,4,9,16,25$?  What do they mean the to "consider each of these values in turn"?
25198
For each $n$ consider the expression $$\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^{n}-\left(\frac{1-\sqrt{5}}{2}\right)^n\right]$$  I am trying to prove by induction that this is an integer for all $n$.  In the base case $n=1$, it ends up being $1$.   I am trying to prove the induction step:   if $\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^{n}-\left(\frac{1-\sqrt{5}}{2}\right)^n\right]$ is an integer, then so is $\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^{n+1}-\left(\frac{1-\sqrt{5}}{2}\right)^{n+1}\right]$.   I have tried expanding it, but didn't get anywhere.
38927
How can I show that $(n-1)!\equiv-1 \pmod{n}$ if and only if $n$ is prime? Thanks.
59795
$p,q$  primes, $(pq,a)=1$ and $p-1|q-1$ then prove $a^{q-1}\equiv 1\pmod{pq}$   Got this in an exam today and had no idea how to do it.
116517
Given a prime $p$ and a natural number $k$, such that $k$ is not divisible by $p - 1$, prove that $\sum_{i = 1}^{p - 1}i^k \equiv 0 \pmod p$.  I split the proof into two cases: one where $k$ is odd and another where it is even.  The case where $k$ is odd can be proven as follows:  $$\sum_{i = 1}^{p - 1}i^k \equiv \sum_{i = 1}^{\frac{p - 1}{2}}i^k + \sum_{i = 1}^{\frac{p - 1}{2}}(-i)^k \pmod p$$  Since $k$ is odd each $(-i)^k = -i^k$, and will cancel with the positive $i$ leaving a zero. Therefore,   $$\sum_{i = 1}^{p - 1}i^k \equiv 0 \pmod p \text{ if $k$ is odd.} $$   I approached the case where $k$ is even in a similar fashion.   $$\sum_{i = 1}^{p - 1}i^k \equiv \sum_{i = 1}^{\frac{p - 1}{2}}i^k + \sum_{i = 1}^{\frac{p - 1}{2}}(-i)^k \equiv 2(\sum_{i = 1}^{\frac{p - 1}{2}}i^k) \space \pmod p$$  Since $p$ is prime, we just need to prove that $\displaystyle\sum_{i = 1}^{\frac{p - 1}{2}}i^k \equiv 0 \pmod p$.  I was stumped after this, so I considered a counterexample, one where $k$ is divisible by $p - 1$. In that I considered a case where $p = 5, k = 8$:  $$1^8 + 2^8 + 3^8 + 4^8 \equiv 1 + 1 + 1 + 1 \space \pmod p$$  This and a few other cases led to the conjecture that all the numbers below $p$ have a mod cycle $(mod \space p)$ that is divisible by $p - 1$. I tested it with $p = 7$.  $2: 2, 4, {\color{red}1}$  $3: 3, 2, 6, 4, 5, {\color{red}1}$  $4: 4, 2, {\color{red}1}$  $5: 5, 4, 6, 2, 3, {\color{red}1}$    After this I was stuck. I couldn't see how this would help me solve the problem. And, more importantly, I couldn't prove my conjecture.
21585
I need help proving or disproving this! If anyone could show me the sequence of steps I can use to help me show the left is equal to the right I would be grateful.  $$\mathcal P(A-B)=\mathcal P(A)-\mathcal P(B)$$
16666
Prove that for for all $p,q\in \mathbb{Z}$, $q&gt;0$ we have: $$ \left| \sqrt{2}-\frac{p}{q} \right| &gt; \frac{1}{3q^2}. $$  To be honest, I do not know where to start - any help would be appreciated.
106823
Let $\{ F_n\}$ be the sequence of numbers defined by $F_1=1=F_2;\, F_{n+1}=F_n+F_{n-1}$ for $n \geq 2$. Let $f_n$ be the remainder left when $F_n$ is divided by $5$. Then $f_{2000}$ equals (A) $0$ $~~~~~~~~~~~~~~~~$ (B) $1$   $~~~~~~~~~~~~~~~~$ (C) $2$$~~~~~~~~~~~~~~~~$ (D) $3$  I found that $F(1)=1$, $F(2)=1$, $F(3)=2$, $F(4)=3$, $F(5)=5$, $F(6)=8$, $F(7)=13$, $F(8)=21$, $F(9)=34$, and $F(10)=55$. But I need a systematic pattern to find $F_n$.
11064
If $p$ and $q$ are distinct primes , prove that $$p^{q-1}+q^{p-1} \equiv 1 \pmod {pq}$$     Using Fermat's Theorem we can get $$p^{q-1} \equiv 1 \pmod q, \qquad q^{p-1} \equiv 1 \pmod p.$$  After that I have no idea at all. Can anyone help me please
25692
If $n\in\Bbb Z^+$ is not a square, prove exist infinitely many primes $p$ such that $\left(\frac{n}{p}\right)=-1$.   Note that if $p\nmid n$ and $n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}$, then $\left(\frac{n}{p}\right)=\left(\frac{p_1}{p}\right)^{\alpha_1}\left(\frac{p_2}{p}\right)^{\alpha_2}\cdots \left(\frac{p_k}{p}\right)^{\alpha_k}$  $=\left(\frac{p_1}{p}\right)^{\alpha_1\pmod {2}}\left(\frac{p_2}{p}\right)^{\alpha_2\pmod{2}}\cdots \left(\frac{p_k}{p}\right)^{\alpha_k\pmod{2}}$  So i.e. prove  exist infinitely many primes $p$ such that $\left(\frac{q_1}{p}\right)\left(\frac{q_2}{p}\right)\cdots \left(\frac{q_n}{p}\right)=-1$, no matter what primes $q_i$ you take.
50174
Let $a,b,c\in\mathbb{R}^*_+$, $abc=1$.  How can i show that $\left(a-1+\frac{1}b\right)\left(b-1+\frac{1}c\right)\left(c-1+\frac{1}a\right)\leq1$ ?  I got $\left(ab-b+1\right)\left(bc-c+1\right)\left(ca-a+1\right)\leq abc=1$, but i can't go any further ...  If i expand it :   $2-ab-\frac{b}a-c-ac-\frac{a}c-b+2a+\frac{2}a-bc-\frac{c}b-a+2b+\frac{2}b+2c+\frac{2}c-4$  Which gives using $c=\frac{1}{ab}$ :   $5ab-\frac{b}a-\frac{1}{ab}-a^2b+\frac{1}a+b+\frac{1}b-2$
79152
$$S=\{a^3+b^3+c^3-3abc|a,b,c\in\Bbb Z\}$$  Can we decide $S$? that is,  we want to find all integers of the form $a^3+b^3+c^3-3abc$.  obviously,    if $m,n\in S$, then $mn\in S$, so we only need to consider primes; if $n\in S$, then $-n\in S$.   Let $f(a,b,c)=a^3+b^3+c^3-3abc$. $f(0,0,0)=0$, $f(1,0,0)=1$, $f(1,1,0)=2$, we get that $0,1,2\in S$  p.s. I find a solution for $a,b,c \geq0$: $n=2^rp_1^{r_1}\dotsb p_s^{r_s}$, $p_1&lt; p_2&lt;...$ are odd primes, then a suficient and necessary condition for $n$ can be expressed as $a^3+b^3+c^3-3abc$($a,b,c \geq0$) is $p_1&gt;3$ or $p_1=3$ with $r_1\geq2$
7048
$$\left(\frac{2}{p}\right) = (-1)^{(p^2-1)/8}$$ how did they get the exponent. May be from Gauss lemma, but how.  Suppose we have a = 2 and p = 11. Then n = 3 (6,8,10), but not  $$15 = (11^2-1)/8$$  n is a way to compute Legendre symbols from Gauss lemma: $$\left(\frac{a}{p}\right) = (-1)^n$$
99288
Let $a \in \Bbb Z$ be such that $a = b^2 + c^2,$ where $b,c \in \Bbb Z \setminus \{0\}.$ Then $a$ cannot be written as $:$   $(1)$ $p d^2,$ where $d \in \Bbb Z$ and $p$ is a prime with $p \equiv 1\ \left (\text {mod}\ 4 \right ).$   $(2)$ $p q d^2,$ where $d \in \Bbb Z$ and $p,q$ are distinct primes with $p,q \equiv 3\ \left (\text {mod}\ 4 \right ).$  $(1)$ is false because $2^2 + 1^2 = 5 = 5 \cdot 1^2,$ where $d = 1 \in \Bbb Z$ and $5$ is a prime with $5 \equiv 1\ \left (\text {mod}\ 4 \right ).$ How do I prove or disprove the other option? Any help in this regard will be appreciated. Thanks for your time.