If $p$ is congruent to $2 \pmod 3$, how can I prove that all $a$, $1 \le a \le p-1$ are cubic residues $\mod p$?  Here's what I've done:  $1^3$ congruent to $1 \pmod p$ thus, 1 is a cubic residue, Also $(p-1)^3=(p-1) \pmod p$ implies  $$(p-1)^3 - (p-1) = (p-1)[(p-1)^2 -1] = (p-1)(p^2 -2p) = p(p-1)(p-2) $$ implies $$p|(p-1)^3 -(p-1)$$ Thus  $p-1$ is a cubic residue $\mod p$. Now I don't know how to show for $1\lt a \lt p-1$ are all cubic residues when $p$ is congruent to $2\pmod 3$.
122659
This problem is from "An Introduction to Number Theory" by Ivan Niven. Define a to be a cubic residue if $x^3 \equiv a \mod p$ has solutions. Prove that if $p=3k+2 ,$ then every number that is in reduced residue system is a cubic residue. And if $p=3k+1$, only one-third of the reduced residues are cubic residues.I did find a solution . But, I've not covered the portion in the book after section 2.5(self-study). I attempted the question in the following way and would appreciate any hints to reach to conclusion:  As $B=\{1,2,\dots ,p-1\}$ is a reduced residue system, it should be enough to prove that $i^3 \equiv j^3\mod p \Rightarrow i\equiv j\mod p$. So, one part of it boils down to  If $p=3k+2$, then show that $p \nmid i^2+j^2+ij $, if $i\neq j \wedge i,j \in B$. I have no idea how to use the $p=3k+2$ part for proving this.
84919
If $a_1, a_2, ..., a_n$ is a reduced residue system $\mod p$ and $a_1', a_2', ..., a_n'$ is another reduced residue system $\mod p$ then $a_1 a_1', a_2 a_2', ..., a_n a_n'$  is not a reduced modulo system $\mod p$.  Not able to show a counter to it. Help Needed.
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.
116134
I'm trying work on problem 11 of Chapter 3 in Ireland and Rosen's Number Theory.   Suppose $\{a_1,\dots,a_{\phi(n)}\}$ is a reduced residue system modulo $n$. Let $N$ be the number of solutions to $x^2\equiv 1\pmod{n}$, then $$ a_1\cdots a_{\phi(n)}\equiv (-1)^{N/2}\pmod{n}. $$  How can this be shown? I know that if $n=p_1^{\alpha_1}\cdots p_m^{\alpha_m}$, then $N=\prod N(p_i^{\alpha_i})$ where $N(p_i^{\alpha_i})$ denotes the number of solutions to $x^2\equiv 1\pmod{p_i^{\alpha_i}}$.   Also, if $x_0$ is a solution, then it is also a solution to $x^2\equiv 1\pmod{p_i}$ for any prime in the factorization of $n$. This implies that $x_0\equiv \pm 1\pmod{p_i}$, so that $x_0$ is coprime to all prime factors of $n$, and thus coprime to $n$.  But I'm not seeing a connection between the left and right hand side products of the congruence in question. Thanks.
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.
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?
46463
proof the integer: From Fermat's little theorem, if $\gcd(a,p) = 1$, then we have: $a^p \equiv a \pmod p$. Since $p$ is only divisible by itself and 1, so we have: $1^p+2^p+3^p+...+(p-1)^p \equiv 1+2 + ...+ p-1 \pmod p$  $\equiv p(p-1)/2$. Since p is odd prime, $p -1 = 2k$. So we have:  $p(p-1) = kp\equiv 0 \pmod p$. Therefore $L_p$ is an integer.  The question is how can I generalize the integer $L_p$ for all odd integers $p$. That is, in the expression for $L_p$ replace the exponent $p$ with another non-constant quantity depend on $p$ in a way that $L_p$ remains an integer for all odd integer $p$, and justify the choice of exponent.
88928
The question is: if $P$ is prime, is $P^{1/3}$ rational?   I have been able to prove that if $P$ is prime then the square root of $P$ isn't rational (by contradiction) how would I go about the cube root?
34817
So, I decided to work with mod $8$ to help develop some intuition on how to generalize the proof. I noticed that taking $a^2$ to clearly be a perfect square, $a^2$ is always congruent to $0,1,-4,4 \mod 8$, at least for a good finite set of cases. Also, I played around with solutions to $3^m + 3^n + 1 = b$ and seen again for a finite set of cases with $m,n$ varying these were always, $b$ is congruent to $-1,5,-5,3$. Now, I see that well only perfect squares produce a set $\{0,1,-4,4\} \mod 8$ and none of the cases I tried to $m,n$ gave me any of the numbers in this set. And now I'm stuck.
96761
I'm in the process of proving Fermat's little theorem.     For a prime integers $p$ we have $a^p \equiv a \mod{p}$   I proved it for a non-negative $a$, not I need to generalize the case to an arbitrary $a \in \mathbb{Z}$. That is, I need to prove that give a negative integer $a$ we have $a^p \equiv a \mod{p}$ using the fact that it is so for a non-negative $a$.
53516
I was given a proof of this in class, but it does not make sense to me, can someone provide a better proof, or explain the one I have provided, thanks.  Suppose $\gcd(a,n) = 1$, where $a$ and $n$ are natural numbers. Prove that $0$, $a$, $2a$, $3a,\ldots, (n-1)a$, is complete residue system modulo $n$.  Proof given in class:  \begin{align*} ka &amp;\equiv ra \pmod{n}\\ &amp;\Rightarrow  k \equiv r \pmod{n}\\ &amp;\Rightarrow  \text{$k-r$ divides $n$}\\ &amp;\Rightarrow \text{$k=r$ because $0\leq k\lt n$, $0\leq r\lt n$} \end{align*}
41028
Show that if $c_1, c_2,\ldots, c_{\phi(m)}$ is a reduced residue system modulo $m$, $m \neq 2$, and $m$ is a positive integer, then $c_1 +\cdots+ c_{\phi(m)} \equiv 0 \pmod{m}$   From the problem statement, I only know that $\gcd(c_i, m ) = 1$. Is there any related theorem that I missed?  A hint would be greatly appreciated.  Thanks, Chan
90886
I'm still making my way along in Niven's Intro to Number Theory, and the title problem is giving me a little trouble near the end, and I was hoping someone could help get me through it.  Now $x^8\equiv 16\pmod{2}$ is solvable with $x\equiv 0\pmod{2}$, so I assume $p$ is an odd prime. From a theorem earlier in the text,      If $p$ is a prime and $(a,p)=1$, then the congruence $x^n\equiv a\pmod{p}$ has $(n,p-1)$ solutions or no solution according as $a^{(p-1)/(n,p-1)}\equiv 1\pmod{p}$ or not.   So since $(16,p)=1$, the problem reduces to showing that $16^{(p-1)/(8,p-1)}\equiv 1\pmod{p}$ holds for all $p$. I note that $(8,p-1)$ can only take values $2,4,8$. For $2$, the above equivalence is then $4^{p-1}\equiv 1\pmod{p}$, which is true by Fermat's little Theorem. For $4$, it is then $2^{p-1}\equiv 1\pmod{p}$, which again holds by FlT. However, the case where $(8,p-1)=8$ is throwing me off. At best I see that $16^{(p-1)/8}\equiv 2^{(p-1)/2}\pmod{p}$, but I'm not sure how to show this is congruent to $1$ modulo $p$. Maybe there's a more elegant way to do it without looking at cases. Thanks for any insight.
56173
Prove $x \equiv a \pmod{p}$ and $x \equiv a \pmod{q}$ then $x \equiv a\pmod{pq}$ for $p\neq q$ distinct primes.  Where can I start with this proof? It looks similar to the Chinese Remainder Theorem, but that deals with two different a values.
46790
So I've said $x^{2}+1$ is reducible over $\mathbb{F}_{p^{n}} \iff \mathbb{F}_{p^{n}}$ contains a root $\alpha$. Hence if $\alpha$ is such a root then $\alpha^2 = -1$ so that $\alpha^4 =1$ and hence $|\alpha|=4$ in $\mathbb{F}^{\times}_{p^{n}}$ and hence $4\mid p^n -1 \implies p^n \equiv 1\bmod 4$. Hence if $p^{n}$ is congruent to $0,2,3$ mod $4$ then $x^{2}+1$ is irreducible over $\mathbb{F}_{p^{n}}$.  My problem is with $p^{n}$ congruent to $1$ mod $4$ being sufficient to conclude that $x^{2}+1$ is reducible. How can I show this?
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?
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.