For how many distinct congruence classes $[a]$ modulo $631$ will there be integer solutions $x$ to the congruence $x^2 \equiv a \pmod{631}$?
122809
So I'm trying to find all solutions of $x^2 \equiv$ $a$ mod $p$ and for some reason the formulas that are suggested everywhere online (for example, ) say that, if p is an odd prime and you have a congruence like this:    Then you can find the solutions with this (if there are any):    That's what I was taught as well, but when entering examples into Wolfram Alpha, I've noticed that there are actually more solutions - these formulas just give you one of them! For example:   If I need to find the solutions of: x^2 ≡ 8 (mod 23) and I use the above formulas, I get the solution: x = +- 13, but  (and it does). So why is that? Why do these formulas only give you 1/2 of the answer and why can't I find a way to find the whole answer (excluding the way where you draw the table with x^2 mod p for x from 0 to p and)?  I realize that I'm probably doing something wrong and I'm not very good at this in the first place, but I've spent hours searching for an answer and couldn't really find anything (that I could understand, at least).
36455
I'm having some trouble figuring out how to give a direct proof using the definitions of mod m and congruence modulo m, without using any theorem involving mod or congruence.  if $a, b, c$ &amp; $m$ are integers such that $m \geq 2$, $c &gt; 0$ and $a \equiv b \pmod{m}$, then $ac \equiv bc\pmod{mc}$
73198
Show that any non-negative rational integer may be written as the sum of two squares if it is of the form $$2^ip_1^{k_1}p_2^{k_2}\cdots p_m^{k_m}q_1^{2j_1}q_2^{2j_2}\cdots q_n^{2j_n}$$ where the $p_1,p_2,\dots,p_m$ are all primes congruent to $1\bmod 4$, the $q_1,q_2,\dots,q_n$ are all primes congruent to $3\bmod 4$ and $i,k_1,k_2,\dots,k_m,j_1,j_2,\dots,j_n$ are all non-negative integers.   I am completely blank on how to form a solution, so help would be much appreciated.
12212
The question is     Suppose p is a prime number and p does not divide a. Prove that the congruence $ax \equiv 1 \mod p$ has a solution   (Without using Fermat's Theorem), I can intuitively tell this is true because since $p$ is prime, every $x &lt; p$ is co-prime to it, thus $$x \mod p$$  Will produce a unique integer for each $x \in \{0, 1, 2, .... p-1\}$, before it cycles over again at $p$. Clearly, some $x$ must have that $x \mod p = 1$. However, I don't know how to prove this for $ax$, mainly because I can't prove the ramifications it can have on the mod cycle. What I do know is that if for some $x$, we have: $$ax \equiv ay \mod p$$ Then since $p$ doesn't divide $a$ (by question assumption), it must divides $x - y$, implying that the solution for $ax \equiv 1 \mod p$ only depends on $x$, however, I don't know how to show this rigorously. Could anyone enlighten me?
12126
I am looking for a hint on this problem:     Suppose $a,b\in\mathbb{N}$ such that $\gcd\{ab,p\}=1$ for a prime $p$. Show that if $a^p\equiv b^p \pmod p$, then we have: $$a^p \equiv b^p \pmod {p^2}.$$   I have noted that $a,b$ are necessarily coprime to $p$ already, and Fermat's little theorem ($x^p\equiv x \pmod p$), but I do not see how I should apply it in this case if at all.  Any hints are appreciated!
34929
The question is: If the number of Sylow $p$ groups is not congruent to $1 \pmod{p^{2}}$, then there exists two distinct Sylow $p$ subgroups $P,Q$ such that $[P : P\cap Q] = [Q : P\cap Q] = p$. I know that whenever $PQ$ is a group, $|PQ| = \frac{|P||Q|}{|P \cap Q| }$ and that there are $1+kp : 1 \leq k \leq p-1$ possible Sylow $P$ subgroups, but I do not know how to proceed.
17561
For which prime numbers p does the congruence $x^2 + x + 1 \equiv 0 \pmod{p}$ have solutions?  We've recently learnt about quadratic reciprocity in class, however I am not sure how to tackle this problem. I have tried starting with the $b^2-4ac$ (discriminant) but that hasn't really helped.
21445
For example: $$7x \equiv 1 \pmod{31} $$ In this example, the modular inverse of $7$ with respect to $31$ is $9$. How can we find out that $9$? What are the steps that I need to do? Update If I have a general modulo equation: $$5x + 1 \equiv 2 \pmod{6}$$ What is the fastest way to solve it? My initial thought was: $$5x + 1 \equiv 2 \pmod{6}$$ $$\Leftrightarrow 5x + 1 - 1\equiv 2 - 1 \pmod{6}$$ $$\Leftrightarrow 5x \equiv 1 \pmod{6}$$ Then solve for the inverse of $5$ modulo 6. Is it a right approach? Thanks.
47380
If $x$ is positive integer, prove that for all integers $a$, $(a+1)(a+2)\cdots(a+x)$ is congruent to $0\!\!\!\mod x$.  Any hints? What are the useful concepts that may help me solve this problem?
11316
How can I solve $x^2 \equiv 19 \pmod {59}$?  I know that we can just try squaring numbers from 1 to 58 , but this is a very slow method, is not their a quicker one?
82944
Let $p$ be an odd prime and $a, b \in \Bbb Z$ with $p$ doesn't divide $a$ and $a$ doesn't divide $b$. Prove that among the congruence's $x^2 \equiv a \mod p$, $\ x^2 \equiv b \mod p$, and $x^2 \equiv ab \mod p$, either all three are solvable or exactly one.  Please help I'm trying to study for final in number theory and I can't figure out this proof.
20254
I'm having some troubles understanding the solution (going from step $2$ to step $3$) of this linear congruence equation. Here's the problem with the solution:   Solve the congruence $2x + 11 \equiv 7 \pmod 3$.   First, we reduce all the coefficients $\pmod 3$:  $$2x + 2 \equiv 1 \pmod 3. \tag{1}$$  Next, we add $1$ to both sides, using the fact that $2 + 1 \equiv 0 \pmod 3$:  $$2x \equiv 2 \pmod 3. \tag{2}$$  Finally, we multiply both sides by $2$, using the fact that $2 · 2 = 4 \equiv 1 \pmod 3$:  $$x \equiv 1 \pmod 3. \tag{3}$$  That is, any number in the set $\{\ldots, −5, −2, 1, 4, \ldots\}$ will solve the original congruence.    Like I said my problem is the step between $(2)$ and $(3)$. If I multiply both sides of $(2)$ by $2$ I get:  $$4x \equiv 4 \pmod 3.$$  Now, I understand that $4$ is congruent to $1 \pmod 3$ so the RHS "simplifies" to $1 \pmod 3$ but I don't understand why the LHS "simplifies" to $x$. Can someone help me with this?
32668
$$\begin{align*} x&amp;\equiv 1\pmod2\\ x&amp;\equiv 2\pmod3\\ x&amp;\equiv 3\pmod4\\ x&amp; \equiv 4\pmod5\\ x&amp;\equiv 5\pmod6\\ x&amp;\equiv 0\pmod7\\ \end{align*}$$  So the solution says we can eliminate $x\equiv 5(\bmod6)$ because the first two cases cover it, but I don't really know how it does. How do we solve it in cases like this where the moduli are not mutually relatively prime.
23138
Problem: Prove that there are infinitely many primes of the type 5 mod 6.  My professor did the problem and the proof was horribly long. Can someone show me a shorter version of the proof of this problem.
80232
Find all the primes $p$ so that $$x^3+x \equiv 1 \pmod p \tag{1}$$ has integer solutions.   We consider $x$ and $y$ are the same solutions iff $x\equiv y \pmod p.$  We can prove that $(1)$ cannot have exactly $2$ solutions unless $p=31$. When $p=31$, the solutions of $(1)$ are $x \equiv {17\text{ (double), } 28} \pmod {31}.$  My question is: when does $(1)$ have no solution, and when does $(1)$ have $1$ solution and when does $(1)$ have $3$ solutions? (As Ma Ming has pointed out, an equation of degree $3$ has no more than $3$ solutions.)  I have proved that if $p \not = 31$, and $a$ is a solution of $(1)$, then $(1)$ has $3$ solutions iff  $$\left(\frac{a-1}{p} \right)=\left(\frac{a+3}{p} \right),$$ here $\left( \frac{a}{p} \right)$ is the Jacobi symbol. Thanks in advance!
27820
In an Introduction to Abstract Algebra by Thomas Whitelaw, he gives examples of the congruence mod operation, such as $13 \equiv5 \pmod4$,  and $9 \equiv -1 \pmod 5$. But when I first learned about the modulo operation my junior year, I would have told you that $13 \equiv 1 \pmod 4$, and that $9 \equiv 4 \pmod 5$.     Is this just a difference in the definition of modulo? Or is this pretty typical (to not take it to the largest factor, or one over)?
45385
What I need to show is that  For $\gcd(ab,p)=1$ and p is a prime, the number of solutions of the equation $ax^2+by^2\equiv 1\pmod{p}$ is exactly $$p-\left(\frac{-ab}{p}\right)\,.$$  I got a hint that I have to use Legendre symbol from the answer. I think that I may count a solution one by one. What I did : $$(ax)^2 \equiv a-aby^2 \pmod{p}$$ It suffices to count $y$ such that $(\frac{a-aby^2}{p})=1$. I tried to use the complete residue system or a primitive root but it didn't work. The factorization also didn't work. I think that the pigeonhole principle may not work because it just says the existence. Thanks in advance.