I ran in to this problem today, and I seem to have trouble.  Suppose $p$ is prime, $p = 1\mod4$, and that $a^2+b^2=p$ with $a$ odd and positive. Show that $(\frac{a}{p}) = 1$.   How can I show that this holds true?
123994
Let a,b be integers and p be an odd prime. if $p$=$a^2+b^2$ and a is odd, prove $(a/p)$ which is legendre symbol = $1$   what i have done is that :   because p and a are odd, b must be even and p is the form of $4k+1$ ($k$ is integer)  and after this, how to prove it ?
83575
Does anyone know how to show this preferable without using modular  For any prime $p&gt;3$ show that 3 divides $2p^2+1$
27033
Let $p$ be prime number ($p\gt2$) and $a,b\in\mathbb Z$ ,$a+b\neq0$ ,$\gcd(a,b)=1$ how to  prove that $$\gcd\left(a+b,\frac{a^p+b^p}{a+b}\right)=1~~\text{or}~~ p$$  Thanks in advance .
41301
Suppose $p$ is a prime number such that $(p-1)/4$ and $(p+1)/2$ are also primes. Show that $p=13$.   My approach:   Since $p$ is prime, it is of the form $6k+1$ or $6k-1$. Now if $p$ is of the form $6k-1$ then $(p+1)/2 = 3k$ which is not possible as $3|3k$.   So $p$ is of the form $6k+1$. Now $(p-1)/4 = 3k/2$ so $2\mid k$. So $p$ is of the form $12k+1$. But now, how to prove $k=1$?  Please help!
99817
From Silverman's A Friendly Introduction to Number Theory, exercise 12.3 (This is not homework). We start with a prime number $p$ and let  $$\sum_{n=1}^{p-1}{\frac{1}{n}} = \frac{A_p}{B_p}$$  where $\frac{A_p}{B_p}$ is a reduced form fraction. The exercise asks to find a simple way to express $A_p$ (mod $p^2$).  I understand that $A_p$ is $0$ (mod $p$), which can be proved by rewriting $A_p$  $$A_p = \sum_{n=1}^{p-1}{\frac{(p-1)!}{n}}$$  and noting that each term in the sum is in the form  $$\frac{(p-1)!}{n}$$  which allows us to write  $$ (p-1)! \equiv -1 \text{ (mod } p)\\ \frac{(p-1)!}{n} \cdot n \equiv -1 \text{ (mod } p)\\ \frac{(p-1)!}{n} \equiv -n^{-1} \text{ (mod } p). $$  Since every number between $1$ and $p$ - $1$ is represented by $-n^{-1}$ (mod $p$) for some unique $n$ between $1$ and $p$ - $1$, we can write   $$A_p \equiv T_{p-1} = \frac{(p-1)p}{n} \equiv 0 \text{ (mod } p).$$  However, the problem only asks for $A_p$ (mod $p^2$), for which I don't know where to proceed. I've tested every prime number up to $p = 37$ and found that with the exception of $p = 3$ every value of $A_p$ is $0$ (mod $p^2$).  If someone who understands what I'm missing can point me in the right direction or give me a hint I'd appreciate it.  EDIT  It's been suggested that Wolstenholme's theorem can be used to finish the proof. The connection between the problem here and Wolstenholme's theorem is interesting so I will try to study Wolstenholme's theorem. However, it doesn't seem like a likely path to have taken from where I'm at in my understanding. I'm also skeptical Silverman had intended for the audience of his book to discover Wolstenholme's theorem as a lemma to proving that $A_p$ is $0$ (mod $p^2$).
4827
I came across this problem and I believe Lagrange's theorem is the key to its solution.  The question is:     Let $p$ be an odd prime. Prove that there is some integer $x$ such that $x^2 \equiv −1 \pmod p$ if and only if $p \equiv 1 \pmod 4$.   I appreciate any help.  Thanks.
27206
a, b are integers. p is prime. I want to prove: $(a+b)^{p} \equiv a^p + b^p \pmod p$  I know about Fermat's little theorem, but I still can't get it I know this is valid: $(a+b)^{p} \equiv a+b \pmod p$ but from there I don't know what to do.  Also I thought about $(a+b)^{p} = \sum_{k=0}^{p}\binom{p}{k}a^{k}b^{p-k}=\binom{p}{0}b^{p}+\sum_{k=1}^{p-1} \binom{p}{k} a^{k}b^{p-k}+\binom{p}{p}a^{p}=b^{p}+\sum_{k=1}^{p-1}\binom{p}{k}a^{k}b^{p-k}+a^{p}$ Any ideas?  Thanks!
19013
I came across a claim that I found interesting, but can't seem to prove for some reason. I have the feeling it should be easy  a prime $p$ can be written in the form $p = a^2 -ab +b^2$ for some $a,b\in\mathbb{Z}$ if and only if $p\equiv 1\bmod{6}$
48862
If $p$ is a prime and $(a,p^2)=p, (b,p^3)=p^2$,calculate $(a+b,p^4)$ $$$$ That's what I thought: $$$$ $$(a,p^2)=p \Rightarrow a=kp$$ $$(b,p^3)=p^2 \Rightarrow b=l p^2$$  So,$$(a+b,p)=(p+p^2)$$  Is it right or am I wrong?
82511
For a prime $p \equiv 1$ or $3$  (mod $8$), show that the equation $x^{2} + 2y^{2} = p$ has a solution.   I'd like to see an elementary proof.
61754
Problem:   If $x^{n-1} \equiv 1 \pmod{n}$, and for all divisors $q$ of $n - 1$, $a^{q} \not\equiv 1 \pmod{n}$, then $n$ is prime. $(n &gt; 1)$   I read the proof in the book and it was very straightforward; however, I wonder is there a way to prove it by just using congruence property?    And another related question about power residue: If we have $a^{n - 1} \equiv 1 \pmod{n}$. Is there any relation between $n - 1$ and $\phi(n)$?  Because I thought of $a^{\phi(n)} \equiv 1 \pmod{n}$, when $(a, n) = 1$. I try to think of away to connect these two ideas, but I still cannot see it. Any idea?    Thanks,
68334
Prove that if $x^2+y^2 \equiv 0\pmod{p}$ where $p$ is a prime and $x,y$ are not both divisible by $p$, then $p \equiv 1 \pmod{4}$.   I tried using that $x^2 \equiv -y^2 \pmod{p}$ and conjectured that $-1$ must a quadratic residue modulo $p$, but I am not sure how that would help.
23115
$(i)$ $a&gt;0,b&gt;0,p&gt;0,q&gt;0$   $(ii)$ $\frac{1}{p}+\frac{1}{q}=1$     How can we prove it?   ${a}{b}≤\frac{a^p}{p}+\frac{b^q}{q}$
113760
Show that if $p$ is any odd prime then $$\left( \frac{q}{p} \right) \equiv q^{\frac{p-1}{2}} \mod p.$$ stating any theory that you use. In particular, you may assume the existence of a primitive element in $G_p$.  Here $\left( \frac{q}{p} \right)$ is the Legendre Symbol and $G_p$ is the group of elements $g \mod p$ such that $\gcd(g,p) = 1$. I said that for some $a \in \mathbb{Z}$, we have $$a \equiv q^{(p-1) / 2} \mod p \implies a^2 \equiv q^{(p-1)} \equiv 1 \mod p$$ by Fermat's little theorem. And so, by definition of the Legendre symbol, we have that if $q$ is a quadratic residue mod $p$ then $\left( \frac{q}{p} \right) \equiv q^{(p-1) / 2} \mod p$. I'm now stuck on how to show that it is $\equiv -1 $ if it isn't a quadratic residue. Obviously the hint with primitive elements comes into play somehow, but I can't see how it does. Can someone help me please.
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.
105980
Let $a$ and $b$ be integers. Show that if $a \equiv b \pmod{p}$ for every prime $p$, then $a = b$. My attempt: Suppose that $p\mid (a-b)$ and $a-b\neq 0$. Then $p\leq|a-b| $. Since the set of prime numbers is infinite we can take $p'$ such that $p\leq |a-b|&lt;p'$. But $p'$ divides $a-b$ as well, thus $p'\leq|a-b|$, which is a contradiction. So $a-b=0$, that is, $a=b$. I am right?
45383
Fermat's little theorem states that if $p$ is a prime number, then for any integer $a$, the number $a^p − a$ is an integer multiple of $p$. In the notation of modular arithmetic, this is expressed as $$a^p \equiv a \mod p.$$  Use Fermat's little theorem to prove that:  Given prime number $p$, show that if there are positive integer $x$ and prime number $a$ such that  $p$ divides   $\frac{x^a – 1}{x – 1}$, then either $а= p$ or $p \equiv 1 \mod a$.  I tried to connect  $\frac{x^a – 1}{x – 1}$ to the theorem, but without any success..  Anything will help.. Thanks in advance