186 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$$ ...
66 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 + ...
68 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$ ...
33k 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 ...
5k 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$ ...
2k 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 ...
10k 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 ...
4k views

### Modular Inverses

I'm doing a question that states to find the inverse of $19 \pmod {141}$. So far this is what I have: Since $\gcd(19,141) = 1$, an inverse exists to we can use the Euclidean algorithm to solve for ...
20k views

### 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 ...
26k views

### Is it possible to do modulo of a fraction

I am trying to figure out how to take the modulo of a fraction. For example: 1/2 mod 3. When I type it in google calculator I get 1/2. Can anyone explain to me how to do the calculation?
25k views

### Finding inverse of polynomial in a field

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$. ...
42k views

### Writing a GCD of two numbers as a linear combination

I am working on GCD's in my Algebraic Structures class. I was told to find the GCD of 34 and 126. I did so using the Euclidean Algorithm and determined that it was two. I was then asked to write it ...
### If a prime $p\mid ab$, then $p\mid a$ or $p\mid b$
If a prime number $p$ is a divisor of a product $ab$, $p$ has to be a divisor of $b$ or $a$. How can I demonstrate this theorem? I demonstrated this theorem on one way using Bezout's theorem in an ...
There exist $x$ and $y$ such that: $\gcd (a,b) = xa + yb$. Why is this true? What's the reasoning behind it?