627 views

How to find integer linear combination [duplicate]

The question said: Use the Euclidean Algorithm to find gcd $(1207,569)$ and write $(1207,569)$ as an integer linear combination of $1207$ and $569$ I proceeded as follows: $$12007 = 569(2) +69$$ ...
78 views

How do I solve this equation over integers: $1=91p+74q$ [duplicate]

Like in title. I need to solve this equation: $$1=91p+74q$$ with $p, q$ being integers. I brute forced the solution to be $(p,q)=(-13,16)$, but I'd love to know how to solve it without just mashing ...
75 views

Bezout identity of 720 and 231 by hand impossible? [duplicate]

Is it possible to solve this by hand? Without using the Extended Euclidean Algorithm We do the Euclidean algorithm and we get: 720 = 231 * 3 + 27 231 = 27 * 8 + 15 27 = 15 * 1 + 12 15 = 12 * 1 + ...
76 views

Finding HCF with the Euclidean Algorithm [duplicate]

Using the Euclidean algorithm, find $\mathrm{hcf}(86, 100)$, and use this to find integers $s, t$ such that $\mathrm{hcf}(86, 100) = 86 · s + 100 · t$. I have that the HCF is 2 but have forgotten what ...
70 views

Finding X and Y for given equation [duplicate]

Given two numbers $A$,$B$. Let $G$ be the GCD of two numbers. I need to tell the values of $X$ and $Y$ such that $$G = X A + Y B$$ How to approach this problem ? Like if we have $A=25$ and $B=45$ ...
42 views

using extended euclidean algorithm to find s, t, r [duplicate]

i am stuck for many hours and i don't understand using the extended euclidean algorithm. i calculated it the gcd using the regular algorithm but i don't get how to calculate it properly to obtain s,t,...
44 views

I don't fully understand this algorithm to solve ax + by = gcd(a,b) [duplicate]

An exercise in my number theory book asks to implement the following algorithm to solve $ax + by = gcd(a,b)$: Set $x = 1$, $g = a$, $v = 0$, and $w = b$ If $w = 0$, set $y = \frac{g-ax}{b}$ and ...
37 views

Determine integers u and v from GCD(308,273) using GCD algorithm [duplicate]

I'm having trouble determining u and v using gcd algorithm, stuck on combining reverse of 308 and 273. I'm lost on what to do after laying out d=rk=... Is there a fixed order to what lines to use? ...
37k views

How to prove: if $a,b \in \mathbb N$, then $a^{1/b}$ is an integer or an irrational number?

It is well known that $\sqrt{2}$ is irrational, and by modifying the proof (replacing 'even' with 'divisible by $3$'), one can prove that $\sqrt{3}$ is irrational, as well. On the other hand, clearly ...
6k views

Linear diophantine equation $100x - 23y = -19$

I need help with this equation: $$100x - 23y = -19.$$ When I plug this into Wolfram|Alpha, one of the integer solutions is $x = 23n + 12$ where $n$ is a subset of all the integers, but I can't seem ...
3k views

$3$ never divides $n^2+1$

Problem: Is it true that $3$ never divides $n^2+1$ for every positive integer $n$? Explain. Explanation: If $n$ is odd, then $n^2+1$ is even. Hence $3$ never divides $n^2+1$, when $n$ is odd. If $n$ ...
3k views

What is an example of a proof by minimal counterexample?

I was reading about proof by infinite descent, and proof by minimal counterexample. My understanding of it is that we assume the existance of some smallest counterexample $A$ that disproves some ...
13k views

How to solve this congruence $17x \equiv 1 \pmod{23}$?

Given $17x \equiv 1 \pmod{23}$ How to solve this linear congruence? All hints are welcome. edit: I know the Euclidean Algorithm and know how to solve the equation $17m+23n=1$ but I don't know how ...
Proof of $\gcd(a,b)=ax+by$
Here is my proof of $\gcd(a,b)=ax+by$ for $a, b, x, y \in \mathbb{Z}$. Am I doing something wrong? Are there easier proofs? $a,b \in \mathbb{Z}, g=\gcd(a,b)$ and suppose $g \neq ax + by$. Let $c$ be ...
I'm having trouble with the procedure to find an inverse of a polynomial in a field. For example, take: In $\frac{\mathbb{Z}_3[x]}{m(x)}$, where $m(x) = x^3 + 2x +1$, find the inverse of $x^2 + 1$. ...