if $p$ is prime and $a\in \mathbb Z$ such that $p\nmid a$, Show that the set $$ R=\{0,a,2a,3a,...,(p-1)a\}$$ Is a complete residue system modulo $p$. This problem is from my textbook. My attempt: I think that the best way to prove it it's by contradiction, so let $x,y \in R$ such that : $$x\ne y, x\equiv y \pmod p$$ and we gonna prove that it's impossible that $x,y\in R$ and $x\equiv y \pmod p$... But I don't know how to do it.
101065
let $p$ be a prime and let $a$ be an integer not divisible by $p$, that is $(a,p)=1$. Then $\{a,2a,3a,...,pa\}$ is a complete residue system modulo $p$.  Since $p\nmid a$, $p\nmid\{a,2a,3a,...,(p-1)a\}$ Since $p|p$, $p|\{pa\}$ which is exactly one element in the set and is therefore a complete residue system.   Wondering if this is an acceptable proof to this theorem.
95106
Prove that if $p$ is a prime having the form $4k + 3$, and if $m$ is the number of quadratic residues less than $\frac p2$, then we have  $$1\cdot3\cdot5 \cdots (p - 2) = (-1)^{m+k+1} \pmod p, \text{ and } 2\cdot4\cdot6\cdots(p - 1) = ( -1)^{m +k} \pmod p.$$  I am stuck with the problem....Help Needed.
63507
If p $\equiv$ 3 (mod 4) with p prime, prove -1 is a non-quadratic residue modulo p.  I suppose this would not be true if p $\equiv$ 1 (modulo 4).  To prove something is a non-square I find to be tricky. It's difficult to see any straightforward way to do this using only the definition of congruence for example.
17873
So far, I know if $p$ is a rational prime, then $(1)$ if $p\equiv 3\mod4$, then $p$ is prime in $\mathbb{Z}[i]$. $(2)$ If $p\equiv1\mod4$  then $p=π_1 π_2$ where $π_1 $ and $π_2$ are conjugate, Then $π_1 $ and $π_2$ are primes in $\mathbb{Z}[i]$. $(3)$ $2=(1+i)(1-i)$, then $(1+i)$and$(1-i)$ are primes in $\mathbb{Z}[i]$.  What's are all the prime elements in Gaussian integers $\mathbb{Z}[i]$? For example, $-3$ are prime in $\mathbb{Z}[i]$, but not in the above $3$ cases.
9820
I need to show that for prime numbers of the form $p=4n+1$, $x=(2n)!$ solves the congruence $x^2 \equiv-1\pmod p$. I then need to show this implies p isn't a gaussian prime.   I have started to solve this using Wilson's theorem that a number $z$ is prime iff $(z-1)!\equiv-1\pmod z$. Therefore the endpoint of my proof should be that $(p-1)!\equiv-1\pmod p$.  As $p$ is of the form $p=4n+1$, I only need to prove that $4n!$ is congruent to $-1$ modulo $p$.   Here is my working so far: Starting with the congruence $x^2 \equiv -1\pmod p$:    $$\eqalign{x^2 = -1\pmod p&amp;\implies   x^2 + 1 = kp \implies (x-i)(x+i) = kp\cr &amp;\implies ((2n)!-i)((2n!)+i))=kp \implies 4n!- 1 =kp\cr}$$   This is where I start to run out of any ideas that seem to get me anywhere. Any tips would be greatly appreciated!
17993
Let $p$ be a prime number. I could already show, that $\mathbb{Z}[\sqrt{-2}]$ is an euclidean domain and that $$p\text{ reducible }\Leftrightarrow\text{ }p=a^2+2b^2\text{ for some $a,b\in\mathbb{Z}$.}$$  Now I wonder how to prove  $$p\equiv 1,2,3\text{ mod }8 \Rightarrow p=a^2+2b^2\text{ for some $a,b\in\mathbb{Z}$.}$$  Maybe there is a possibility to show  $$p\equiv 1,2,3\text{ mod }8 \Rightarrow p\text{ reducible }?$$
104818
Theorem: There are infinitely many primes congruent to $3 \mod 4$. Proof: Assume that $p_1 = 3, . . . , p_n$ are primes of the form $p_j ≡ 3 \mod 4$. We will construct a new one by looking at $N = 4p_1 · · · p_n − 1$ (putting $N = 4p_1 · · · p_n+3$ would also work).  There is more to this proof but the rest of it I understand, what I don't get is where it says &quot;$N = 4p_1 · · · p_n − 1$ (putting $N = 4p_1 · · · p_n+3$ would also work)&quot;. I do not understand why we are writing $4p_1 · · · p_n − 1$. Is there a more clear way to prove this theorem?
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.
71932
I am stuck with this exercise:     Show that $\forall s &gt;0 \quad \exists N &gt;0$ such that $$x^2 \equiv 1\pmod N$$ has more than $s$ solutions.   I think I cannot use the theory if quadratic residues, because the modulus is not prime, so maybe I must prove it with square roots or roots of unity, but I don't know how to approach it at all.  Thanks for any help.
102960
Let $p$ be a prime number. Let $R$ be the subset of all rational numbers $m / n$ such that $n \neq 0$ and $n$ is not divisible by $p$. Show that $R$ is a ring. My Proof-trying. $R1$. Associativity for under addition is clear. $R2$. $\dfrac {m} {n}+0=0+\dfrac {m} {n}$, so there exist the identitiy element for under addition. $R3$. $\dfrac {m} {n} + \dfrac {-m} {n}=\dfrac {-m} {n} +  \dfrac {m} {n}$, so there exist inverse element. $R4$. $\dfrac {m} {n} + \dfrac {m'} {n'}=\dfrac {m'} {n'}+\dfrac {m} {n}$, so commutativity. So $R$ is an additive abelian group. $R5$. $\dfrac {m} {n} ( \dfrac {r} {s} + \dfrac {t} {v})=\dfrac {mr} {ns} + \dfrac {mt} {nv}$ and $( \dfrac {r} {s} + \dfrac {t} {v})\dfrac {m} {n}=\dfrac {rm} {sn}+\dfrac {r} {s}+\dfrac {tm} {vn}$ $R6.$ $R$ is associativity for under multiplication, clear. $R7.$ $1 \dfrac {m} {n}=\dfrac {m} {n} 1 = \dfrac {m} {n}$, so there exist identity element for under multiplication. Can you check my answer? If false, can you write true answer?
62474
I want to prove that if $p$ is a prime and $x,y \in \mathbb{Z}$, then $$(x+y)^p \equiv x^p+y^p \pmod{p}$$  So far I know that $$(x+y)^p = \sum_{k=0}^{p} \dbinom{p}k x^{p-k} y^k$$  A part of the above equation is supposed to cancel, I think, but I can't figure out a way how to make it cancel.
25177
Assume: $p$ is a prime that satisfies $p \equiv 3 \pmod 4$  Show: $x^{2} \equiv -1 \pmod p$ has no solutions $\forall x \in \mathbb{Z}$.  I know this problem has something to do with Fermat's Little Theorem, that $a^{p-1} \equiv 1\pmod p$. I tried to do a proof by contradiction, assuming the conclusion and showing some contradiction but just ran into a wall. Any help would be greatly appreciated.
118428
Let $p=2^{2^k}+1$ be a prime where $k\ge1$. Prove that the set of quadratic non-residues mod $p$ is the same as the set of primitive roots mod $p$. Use this to show that $7$ is a primitive root mod $p$.  I've already shown the theorem to be true. The second part asks to use the first part to show the result which leads me to think that I have to show $7$ is a quadratic non-residue mod $p$ then use the first part to imply that it must be a primitive root.   To show $7$ to be a quadratic non-residue for $k\ge1$ is to show that the Legendre symbol $\left(\frac{7}{p}\right) = -1$. Now, $$\left(\frac{7}{p}\right)=\left(\frac{p}{7}\right)(-1)^{\left(\frac{7-1}{2}\right)\left(\frac{p-1}{2}\right)} = \left(\frac{p}{7}\right)(-1)^{3(2^{(2^k)-1})} = \left(\frac{p}{7}\right)$$ since $2^{2^k-1}$ is even (as $k\ge1$).  Then it suffices to know $p$ mod $7$ to determine the Legendre symbol. Since $\left(\frac{p}{7}\right) = -1$ when $p\equiv 3,5,6$ mod $7$, I suspect I somehow have to show that $p$ must be congruent to those values but I don't know how to do that. Although, trivially, $p\not\equiv 1$ mod $7$ otherwise, $7|2^{2^k}$ which is not possible.  Unfortunately, I don't know where to go from here.  Any guidance would be appreciated. However, assuming I’ve taken the right approach, I would prefer a constructive hint to a full blown solution, as I think I may be able to work it out on my own, given a nudge in the right direction.  Thank you for taking the time.
114504
This is another one of the number theory problems I've been struggling with as of late (hopefully I'm not posting too many questions at once!).     Let $n$ be a positive integer and let $p=2^n+1$ be a prime number.   Prove that every quadratic nonresidue modulo $p$ is a primitive root   modulo $p$.   Suppose $a$ is a quadratic nonresidue and $r$ a primitive root muodulo $p$. Then there exists no $x$ such that $x^2 \equiv a \mod p$. We must determine the order of $a$. We know that $a$ must be congruent to some power of $r$, say $m$, since $\{r^1,r^2,\ldots,r^{2^n}\}$ is a reduced residue system modulo $p$. Suppose that $\mathrm{ord}_p a=b$. Then $a^b \equiv r^{mb} \equiv 1 \mod p$. We must show that $b=2^n$ since $\phi(p)=2n$. But $r$ is a primitive root and so $mb \equiv 0 \mod{2^n}$ (or $\equiv 2^n \mod{2^n}$). Hence $mb = 2^n k$. How can I finish it?
83924
I've stumbled upon this congruence very similar to Fermat's Little Theorem, but I can't seem to wrap my head around how to solve it. It goes like this:     i) Suppose $p$ is prime, $(a,p)=1$ and the congruence $x^2 \equiv a \pmod p$ has a solution $x$. Prove that $a^{(p-1)/2}\equiv 1 \pmod p$.   And the same question but with an additional condition:     ii) Suppose $p$ is prime, $p \equiv 3  \pmod 4$, $(a,p) = 1$ and the congruence $x^2 \equiv a \pmod p$ does not have a solution $x$. Prove that $a^{(p-1)/2}\equiv -1 \pmod p$.   For i: Since $x^2 \equiv a \pmod p$ has a solution, we know that $p \mid x^2 - a$, hence $kp=x^2-a$ for some integer $k$, or $a = x^2-kp$. Now this doesn't really help me much!  For ii: Similarly stumped.
4812
Problem: $(\forall a\in\mathbb{Z^+})(m\in\mathbb{Z^+}\to a^m\equiv a^{m-\phi(m)}\pmod{m})$  My work: Start by letting $m=p_1^{a_1}p_2^{a_2}\cdots p_r^{a_r}$. If $(a,p_i)=1$ for some integer $i$, then we have that  $$ a^{\phi(p_i^{a_i})}\equiv 1\pmod{p_i^{a_i}} $$ by Euler's theorem. Since $\phi(p_i^{a_i}) \mid \phi(m)$, we have that $p_i^{a_i}\mid (a^{\phi(m)}-1)$ if $(a,p_i)=1$.   Beyond this, I am stuck at the moment.
116479
Prove that if $p$ and $p+2$ are both prime integers greater than $3$, then $6$ is a factor of $p+1$.  Computing a few primes greater than $3$ modulo $6$ shows the following pattern $5,1,5,\dots$ Thus $$\begin{cases}p\equiv1,5 \pmod{6} \\ p+2 \equiv3,7 \equiv3,1 \pmod{6}\end{cases}$$ Also $p+1 \equiv 2,6 \equiv2,0 \pmod{6}$. I'm not sure how to continue from here... I would like to use modular arithmetic to show this. Is it necessary to remember that every prime can be written as $6n+1$ or $6n+5$ here?