# Questions tagged [euclidean-algorithm]

For questions about the uses of the Euclidean algorithm, Extended Euclidean algorithm, and related algorithms in integers, polynomials, or general Euclidean domains. This is **not** about Euclidean geometry.

659 questions
Filter by
Sorted by
Tagged with
0answers
25 views

### Methods of Computing the Inverse of Y Mod X [duplicate]

I was wondering what methods exist for computing the inverse of Y mod X? Of these, which is the most efficient (time-wise)? I am aware of the Extended Euclidean Algorithm already, just curious what ...
1answer
103 views

### Proving $\gcd(ga, gb) = g\gcd(a, b)$ intuitively [duplicate]

I am trying to derive by myself $$\gcd(ga, gb) = g\gcd(a,b),$$ but I am stuck proving it fully. Note, that I avoided reading the relevant proof as I am trying to improve my intuition on the process ...
0answers
44 views

### Breaking down eucliclean algorithm as a series of movements of the numbers across the number line

I was going over a process that tries to show the euclidean algorithm distilling it to a series of movements across the number line. The basic movements are measured by the $2$ numbers that we are ...
0answers
32 views

### Reckoning or anthyphairesis: process and intuition

I encountered the process called "Anthyphairesis" which apparently was the basis of the Euclidean algorithm and was also described in Chinese writings under the name "reckoning". A ...
0answers
7 views

### Calculating the Euclidean distance of joint probabilities

I am reading a paper and in this paper they generate a fake tabular dataset similar to the a real tabular dataset. The dataset could be considered to have records of people like their age, their ...
0answers
29 views

1answer
38 views

3answers
52 views

### Finding all numbers smaller than $2040$ so that $51 | 71n-24$ [duplicate]

This is a Number Theory problem about the extended Euclidean Algorithm I found: Use the extended Euclidean Algorithm to find all numbers smaller than $2040$ so that $51 | 71n-24$. As the eEA always ...
1answer
223 views

### Let $a$ and $b$ be positive integers. If $b=ak$ for some $k \gt 0$ then $2^b − 1 = (2^a)^k − 1 = (2^a − 1)m$ for some $m$. [duplicate]

I came across a homework question asking if this is true or false. After plugging in some numbers, this turned out to be true. May I know a proof or explanation for this? I sort of know this is ...
1answer
89 views

4answers
42 views

### Find the GCD of a polynomial using the extended Euclidean algorithm and express it in the form $a(x)f(x)+b(x)g(x)$ [duplicate]

I am working on a problem that I can not seem to finish. Find the gcd of $f(x)=x^7+1$ and $g(x)=x^6+x^5+x^3+1$, and express it in the form $a(x)f(x)+b(x)g(x)$ using the extended euclidean algorithm. I ...
2answers
28 views

2answers
64 views

### Given that 𝑎 and 𝑏 are positive integers with $𝑎\mid𝑏$, how would one prove that $\gcd(𝑎, 𝑏) = 𝑎$? [duplicate]

I'm having trouble showing that if 𝑎 and 𝑏 are positive integers with 𝑎|𝑏, then 𝑔𝑐𝑑(𝑎, 𝑏) = a. I'm aware that the greatest common divisor of two numbers is the largest number that is a ...
2answers
86 views

0answers
31 views

0answers
23 views

1answer
35 views

1answer
68 views

### How to find a pair of solutions of Linear Diophantine equation such that you minimize this expression?

This is a typical Math coding Problem I encountered here Problem. So Let me break it to you Suppose you have two values $a$ and $b$ and to select this value $a$ one time it takes you $c_1$ cost and ...
0answers
48 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 ...
2answers
92 views

### Application of extended Euclidean algorithm

I tried applying the algorithm from Wikipedia in order to calculate $-133^{-1}\mod 256$ I spent already time myself finding the mistake but no success. This is how I did go about applying the ...