Below is text from the book Joseph H. Silverman: A Friendly Introduction to Number Theory, 4th Edition, chapter 8, page 56.  To solve $4x\equiv 3 \pmod{19}$ we will multiply both sides by $5$. This gives $20x\equiv 15 \pmod{19}$ But $20\equiv 1\pmod{19}$, so $20x\equiv x\pmod{19}$ Thus the solution is $x\equiv 15\pmod{19}$  I was wondering if I can document the steps on how this is done to solve a generic congruence - I know this can be done only for solving congruences with small numbers To solve $Ax\equiv B \pmod{m}$ Find P &amp; Q such that they satisfy the following conditions  Q = A * n P = B * n $Q \equiv 1 \pmod{m}$  Once you do this - you can easily solve the congruence.  I have 2 questions  Is this correct - i.e. my description of the steps of how the example in the book was solved?  This seems to work when gcd(A, m) = 1. Will this work if the gcd is not 1.
15178
When I am faced with a simple linear congruence such as  $$9x \equiv 7 \pmod{13}$$ and I am working without any calculating aid handy, I tend to do something like the following:  "Notice" that adding $13$ on the right and subtracting $13x$ on the left gives: $$-4x \equiv 20 \pmod{13}$$  so that $$x \equiv -5 \equiv 8 \pmod{13}.$$  Clearly this process works and is easy to justify (apart from not having an algorithm for "noticing"), but my question is this: I have a vague recollection of reading somewhere this sort of process was the preferred method of C. F. Gauss, but I cannot find any evidence for this now, so does anyone know anything about this, or could provide a reference? (Or have I just imagined it all?)  I would also be interested to hear if anyone else does anything similar.
90960
Let $x$ and $y$ be integers not congruent to $0$ modulo $p$ where $p$ is a prime. Prove that if $p \equiv 3 \pmod{4}$ then $x^2+y^2 \not \equiv 0 \pmod{p}$.   I thought about proving this algebraically and by contradiction. So we say $x^2+y^2 = pz$ and have to show this is impossible.
62281
Question : Do there exist an infinite number of integer-solutions $(x,y,z)$ of $x^x\cdot y^y=z^z$ where $1\lt x\le y$ ?  Motivation : After struggling to find a solution, I've just got one solution, which is  $$(x,y,z)=(1679616, 2985984, 4478976).$$  In the following, I'm going to write how I got this solution.  Letting $d$ be the greatest common divisor of $x,y,z$, we can represent $$x=ad, y=bd, z=cd$$ where $a,b,c$ are coprimes with each other. Then, we get $$d^{a+b-c}\cdot a^a\cdot b^b=c^c.$$  In the following, let's consider without the condition $x\le y$. Here, I suppose  $$a=2^m, b=3^n, a+b-c=1.$$  (As a result, this supposition works.)  Then, we get $$d=\frac{c^c}{2^{ma}\cdot 3^{nb}}.$$  Hence, letting $c=2^k\cdot 3^l$, if  $$kc\ge ma=m\cdot 2^m, lc\ge nb=n\cdot 3^n,$$ then $d$ is an integer.  Since $(m,n)=(4,2)$ satisfies the above conditions, then we get $d=2^8\cdot 3^6=186624.$ Hence we can get  $$x=9d=2^8\cdot 3^8=1679616, y=16d=2^{12}\cdot 3^6=2985984, z=24d=2^{11}\cdot 3^7=4478976.$$ Note that here I interchanged $x$ and $y$.  P.S : I was surprised to get this solution because I got this almost by chance. So, I don't know the other solutions. If you have any helpful information, please teach me.
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.
105231
What solutions does the equation $4x\equiv2\mod10$ have? (Hint, it will have more that one.) What about solutions to an equation $ax\equiv d\mod n$, where $d=\gcd(a,n)$?  This is the question that appeared in our universities last year paper. But it seems very difficult for me like for first part I am able to solve by simplifications I got $x=5\cdot Z +3$ as solution which makes sense and seems fair but for the second one, I have no idea how can I approach that. Can you please help me out with that one. I tried to simplify that by using Euclidean algorithm but still, I didn't get any idea that what actually the solution will be. My final exam is on 2nd of next month and because of covid I am unable to contact in person for any help. So any help from this site will be appreciated. Thank you for looking at this question!
64493
I need to describe all numbers of the form $x^2 + 2y^2$.  So far I've reduced the problem to primes, and showed p=2 satisfies it. I've also shown that any primes mod 5 or 7 can't be a written in this form. How do I proceed to show that it holds for all primes mod 1 or 3? I think I'll need to use quadratic reciprocity somehow (only since it is the topic of the homework). I have a hunch the supplementary quadradic recprocity laws will be important.  Any help would be appreciated. Thanks!
73445
Find an integer having the remainders $2,3,4,5$ when divided by $3,4,5,6$, respectively.   My work:  We consider the congruences $x \equiv 2 \pmod 3$, $x \equiv 3 \pmod 4$, $x \equiv 4 \pmod 5$, $x \equiv 5 \pmod 6$. We can reduce this further to $x \equiv 2 \pmod 3$, $x \equiv 3 \pmod 4$, $x \equiv 4 \pmod 5$. We have  $N_1 = 4 \cdot 5 = 20 \implies 20 x_1 \equiv 1 \pmod{3} \implies 2x_1 \equiv 1 \pmod{3} \implies x_1 \equiv 2 \pmod {3}$  $N_2 = 3 \cdot 5 = 15 \implies 15x_2 \equiv 1 \pmod{4} \implies -x_2 \equiv 1 \pmod{4} \implies x_2 \equiv 3 \pmod {4}$   $N_3 = 3 \cdot 4 = 12 \implies 12 x_3 \equiv 1 \pmod{5} \implies 2x_3 \equiv 1 \pmod{5} \implies x_3 \equiv 3 \pmod {5}$  Now,  \begin{align*} \bar x &amp;= a_1 N_1 x_1 + a_2 N_2 x_2 + a_3 N_3 x_3 \\ &amp;= 3 \cdot 20 \cdot 2 + 4 \cdot 15 \cdot 3 + 5 \cdot 12 \cdot 3 \\ &amp;= 480 \equiv 0 \pmod {3 \cdot 4 \cdot 5} \end{align*}  Is this correct, or is something wrong in my work? I don't like how I have $0$ remainder.
69034
Show that there is no solution to the congruence $x^2\equiv3\bmod5$.   I'm not sure if the fact that the only numbers divisible by $5$ are those ending in $0$ or $5$ will help&hellip;
80346
I'm having some trouble proving the following proposition:  Let $m \in \mathbb N$ and $a,b,k \in \mathbb Z$, then: $$ka \equiv kb \pmod{m} \iff a \equiv b \pmod{\frac{m}{\gcd(k,m)}}$$  I began by trying to prove that $a \equiv b \pmod{\frac{m}{\gcd(k,m)}} \implies ka \equiv kb \pmod{m}$ but I got stuck with: $$a\gcd(k,m) \equiv b \gcd(k,m) \pmod{n}$$ Then I also tried to prove that $ka \equiv kb \pmod{m} \implies a \equiv b \pmod{\frac{m}{\gcd(k,m)}}$ But I also was not able to conclude anything. This is my first time learning modular arithmetic and I'm still confused with the concepts and have no intuition with this at all, this is perhaps why I'm having some trouble solving these types of questions. How can I prove this?
59847
I am trying to find all integers that give remainders 1,2,3 when divided by 3,4,5 respectively.  So I start defining  $$a_1=1, a_2=2, a_3=3,$$$$ m_1=3, m_2=4, m_3=5,$$$$ m_1m_2=12, m_1m_3=15, m_2m_3=20,$$$$ m=60$$ All the moduli are pairwise coprime, so by the Euclidean Algorithm $$12x+5y=1\Rightarrow x=-2, y=5.$$ $$15x+4y=1\Rightarrow x=-1, y=4.$$ $$20x+3y=1\Rightarrow x=-1, y=7.$$ Therefor a solution should be  $$20\cdot(-2)\cdot1 +15\cdot (-1)\cdot 2+12\cdot (-1)\cdot 3=-40-30-36=-106$$ But under mod 60, this implies a solutions should be of the form, $60t+14$.  But it is not.  THis is not right.  Why did this technique not work?
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?
26908
Let $p, q$ be distinct odd primes, I would like to compute the number of solution $\mod p$ to the congruence $x^q \equiv 1 \mod p$. (Show that it's $gcd(q, p - 1))$  If $x^q \equiv 1 \mod p$, since $q$ is prime, this must mean that $x$ is either $1$ or has order $q$.   Hence, the problem reduces to finding the number of elements of $U_p$ which is either $1$ or has order $q$.  If $ q \nmid  p - 1$, then there is only one element, namely $1$.  If $q \mid p - 1$, then the number of elements of order $q$ is $\phi(q) = q - 1$, and so the number of solutions to the congruence $\mod p$ is $q - 1 + 1 = q$, and in either case the number of solutions is $\gcd(q, p - 1)$.  Does this look fine?
64155
I was working on a problem that resulted in the calculation: $20 \equiv 10x \pmod{11}$.  I got the answer $x \equiv 2 \pmod{11}$ with the thought process: Since $10$ is a factor of $20$ I can rewrite $20 \pmod{11}$ as $10x \pmod{11}$ with $x=2$. But isn't this basically the same as using division, which we aren't supposed to do in modular spaces?  If I solve by multiplying $20$ by the multiplicative inverse of $10 \pmod{11}$ which is $10$, I get $200 \pmod{11}$ which simplifies to $2 \pmod{11}$ anyway. Did these numbers just happen to be the same or is my original method valid?
14553
Can someone explain me how this type of examples are being solved? I know that I can watch this example like this $2001^{n}\equiv 1\ ({\rm mod}\ 2^{2002})$ but I don't know what to do when the divisor is such a large number like $2^{2002}$  $2^{2002}|2001^{n}-1$
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}$
57117
Find out all solutions of the congruence $x^2 \equiv29 \mod 5$.  [Hint:Find the solutions of this congruence $\mod 5$ , $\mod 7$ , and $\mod 7$ , and then use the Chinese Remainder Theorem.]
49397
How to solve $ 13x \equiv 1 ~ (\text{mod} ~ 17) $?   Please give me some ideas. Thank you.