How do you solve the equation $ax\equiv b \pmod m$ with the extended Euclidean algorithm? I saw that you could solve the Diophantine equation $ax-my=b$ I've seen examples but I'm still a bit confused. (Sorry if this sounds stupid)
3509
What is the best way to solve equations like the following:  $9x \equiv 33 \pmod{43}$  The only way I know would be to try all multiples of $43$ and $9$ and compare until I get $33$ for the remainder.  Is there a more efficient way ?   Help would be greatly appreciated!
79310
The problem is what are the integer solutions to  $$7x^2 - 40xy + 7y^2 = (|(x - y)| + 2)^3$$  I only got $x - y = 4 (\mod 13)$. Also, how to solve it?
35604
I need to solve $3x^2 + 6x +1 \equiv 0 \pmod {19}$  I saw the same problem here -     but didn't understand how he got to the conclusion   $x(x+2) \equiv 6 \pmod {19}$  and anyway im trying to solve it how we learned in class -   multiply both sides and the modulo by $4a$ then solve the two equations  $y^2 \equiv b^2 -4ac \pmod {4an}$  $2ax + b \equiv y \pmod {4an}$  so I tried multiplying the hole thing by $4a$ , that is $4 \times 3$  and got to $(2 \times 3x + 6)^2 \equiv 36 -4 \times 3 \pmod {19 \times 4 \times 3}$  now I am stuck . any help will be appreciated
25251
We want to find the solution $x$ to the congruence system  $$\begin{align} x &amp;\equiv r_1 \!\!\!\pmod{\!m_1}\\ x &amp;\equiv r_2 \!\!\!\pmod{\!m_2}\end{align},\ \ {\rm where}\ \  \gcd(m_1, m_2) = 1$$  These can be rewritten as  $$\begin{align} x &amp;= r_1 + m_1 j\\ x &amp;= r_2 - m_2k\end{align}$$  for unknown integers $j, k$. So we set those two equations as equal and rearrange them to  $$m_1j + m_2k = r_2 - r_1$$  Now assume we perform $\text{egcd}(m_1, m_2)$, which gives us the solution to  $$m_1u + m_2v = \gcd(m_1, m_2)$$  Let the integer $\,h\,$ make $\,h \gcd(m_1, m_2) = r_2 - r_1$.  Then $\qquad hm_1u + hm_2v = h\gcd(m_1, m_2) =  r_2 - r_1 = m_1j + m_2k$  At this point I am lost because I don't think we can just assume  $hm_1u = m_1j$ and extract $j = hu$.   How do I get the values of $j$ or $k$ so I can get the value of $x$?
93879
The problem I am given is finding a solution to the following pair of equations:  $3x + 4y$ $\equiv$ $5$ $mod$ $13$  $2x + 5y$ $\equiv$ $7$ $mod$ $13$  By reading the methodology here:   Since the modulos in my problem are also the same, I am able to use substitution, but this leaves fractions in my expressions.  I then used matrix multiplication as follows:  $\begin{bmatrix} 3 &amp; 4\\ 2 &amp; 5\end{bmatrix}$ $\begin{bmatrix}\ x\\ y\end{bmatrix}$ = $\begin{bmatrix}\ 5\\ 7\end{bmatrix}$   And solving this also gives me a matrix with fractions, so I am a bit lost on how to solve this problem.  Any help is appreciated. Thank you very much.
24393
I have the following equation: $$ n \equiv M^k\mod(b) $$ where n, a, b are integers, and M is unknown. How do I solve this equation to find the M value? Those a and b are public keys of the RSA algorithm and n is the result of encryption. I need to find the encrypted message.
119411
I want to find all $ a \in \mathbb N $ such that $2^a − 1 \equiv 0 \pmod 3$  and $ 4x^2 + 1 \equiv 0 \pmod {\frac{2^a -1}{3}}$ has a solution. I know the approach is to first prove that $a$ should be a power of 2. But I am not able to solve this question.
52291
I know that there exists at least one solution, because $ax \equiv b \mod m \implies ax - b = qm$  Rearranging terms gives $ax - qm = b$, and since $d | a$ and $d | m$, so $d | b$ it can be said that $b \equiv 0 \mod d$.  I implemented Euclid's extended algorithm and have been able to experimentally verify that the claim holds, but I do not see a pattern or how I can begin to show there are exactly $d$ solutions.  def euclid_extended(x, y, i=0):   if y == 0:     print("iteration {0} returns ({1}, {2}, {3}) - base case hit with ({4}, {5})".format(i, x, 1, 0, x, y))     return (x, 1, 0)   else:     (d, a, b) = euclid_extended(y, x % y, i + 1)     print("iteration {0}. ({4}, {5}) =&gt; ({1}, {2}, {3})".format(i, d, b, a - b * (x//y), x, y))     return (d, b, a - b * (x//y))
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.
5262
Let $A ∈ M_{m\times n}(\mathbb{Q})$ and $B ∈ \mathbb{Q}^m$. Suppose that the system of linear equations $AX = B$ has a solution in $\mathbb{R}^n$. Does it necessarily have a solution in $\mathbb{Q}^n$?  Where do I start?    I feel I can use this to :  $$x_i=\frac{1}{a'_{ii}}\left(b'_i - \sum_{j=i+1}^{k} a'_{ij} x_j \right).$$    Here is a thought that just crossed my mind, but I'm not sure if this is legal:  Suppose $Y\in \{\mathbb{R}\setminus \mathbb{Q}\}^n$ and $Y'\in\mathbb{Q}^n$ are solutions to $AX=B$. Then $AY=AY'=B$, or $A(Y-Y')=A(Y+(-Y'))=0$, but  addition between $\{\mathbb{R}\setminus \mathbb{Q}\}^n$ and $\mathbb{Q}^n$ is . . .
6364
When given $p = 5, q = 11, N = 55$ and $e = 17$, I'm trying to compute the RSA private key $d$.  I can calculate $\varphi(N) = 40$, but my lecturer then says to use the extended Euclidean algorithm to compute $d$. That's where I get stuck.    Here's my work so far:  First I use the Euclid algorithm to calculate:  40 = 2(17) + 6  17 = 2(6) + 5 6 = 1(5) + 1 = gcd   So I know the GCD is 1. Applying the 'extended' section of the algorithm:  6 = 40-2(17) 5 = 17-2(6) 1 = 6-1(5) 1 = 6-1(17-2(6)) 3(6) = 1 (17) 3(40 - 2(17)) - 1(17) 3(40) - 3(17)   I know the answer is $33$, but I have no idea how to get there using the extended Euclidean algorithm. I can't figure out why I'm getting $3(40) - 3(17)$ when I know the answer should contain $33$.
108601
Exercise $12$ in Section $1.6$ of Nathanson's : Methods in Number Theory book has the following question.         When is the sum of a geometric progression equal to a power? Equivalently, what are the solutions of the exponential diophantine equation $$1+x+x^{2}+ \cdots +x^{m} = y^{n} \qquad \cdots \ (1)$$ in integers $x,m,n,y$ greater than $2$? Check that    \begin{align*} 1 + 3 + 3^{2} + 3^{3} + 3^{4} &amp; = 11^{2}, \\\ 1 + 7 + 7^{2} + 7^{3} &amp;= 20^{2}, \\\ 1 + 18 +18^{2} &amp;= 7^{3}. \end{align*}   These are the only known solutions of $(1)$.      The  doesn't reveal much about the above question. My question here would be to ask the following:   Are there any other known solutions to the above equation. Can we conjecture that this equation can have only finitely many solutions?   Added: Alright. I had posted this question on  some time after I had posed here. This user by name  had actually given me a link which tells more about this particular question. Here is the link:
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).
57250
What I have done is this:  $a\equiv b \pmod{2n}$,  $a=b+c\times2n$, for some $c$,  $a^2=b^2+2b\times c\times2n+c^2\times2^2n^2$,  $a^2-b^2=(b\times c+c^2n)\times4n$, then  $a^2\equiv b^2\pmod{2^2n}$.  I think that this is right: what I DON’T understand is how to generalize this to:  $a\equiv b\pmod{kn}\Rightarrow a^k\equiv b^k \pmod{k^2n}$.  Please give me a hint.
14071
I want to find a set of integer solutions of Diophantine equation: $ax + by = c$, and apparently $\gcd(a,b)|c$. Then by what formula can I use to find $x$ and $y$ ?   I tried to play around with it: $x = (c - by)/a$, hence $a|(c - by)$.     $a$, $c$ and $b$ are known. So to obtain integer solution for $a$, then $c - by = ak$, and I lost from here, because $y = (c - ak)/b$. I kept repeating this routine and could not find a way to get rid of it? Any hint?  Thanks, Chan
26708
I'm currently learning how to find the inverse of a modulo with the Extended Euclid Algorithm and I stumbled upon a problem when finding an inverse when the $m&gt;p$ as for $m \equiv 1 \pmod{p}$  For example, in $$ 240x \equiv 1 \pmod{17} $$ what is the inverse? What are the steps to find it?
1810
I know it might be too easy for you guys here. I'm practicing some problems in the textbook, but this one really drove me crazy. From $\gcd( a, b ) = 1$, I have $ax + by = 1$, where should I go from here? The extra $ac$ is so annoying. Any hint?    Thanks, Chan