Linked Questions

0
votes
1answer
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$$ ...
-1
votes
2answers
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 + ...
0
votes
1answer
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$ ...
145
votes
12answers
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 ...
34
votes
9answers
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 ...
11
votes
10answers
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$ ...
8
votes
4answers
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 ...
6
votes
9answers
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 ...
7
votes
5answers
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 ...
12
votes
2answers
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 ...
11
votes
6answers
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?
13
votes
5answers
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$. ...
8
votes
3answers
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 ...
5
votes
9answers
949 views

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 ...
3
votes
5answers
12k views

Proof of Extended Euclidean Algorithm?

There exist $x$ and $y$ such that: $\gcd (a,b) = xa + yb$. Why is this true? What's the reasoning behind it?

15 30 50 per page