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.
789
questions
-2
votes
1
answer
58
views
find {p/q}+{2p/q}+{3p/q}...{(q-1)p/q}, where p and q primes and {x}= x - floor x [duplicate]
I have been trying this problem for some time and reached somewhere using euclids division algorithm. Any help would be appreciated
0
votes
1
answer
50
views
An estimation of Bezout Coefficients(produced by Extended Euclidean Algorithm) on Gaussian integers
Problem: Suppose that for two given Gaussian integers $a$ and $b\ (|a|>|b|>0)$, there exists $a_0$ such that the remainder of the Euclidean division of $a_0$ by $a$ is exactly $b$. If it takes $...
- 49
0
votes
1
answer
92
views
Extended euclidian algorithm
I'm trying to understand how the matrix form of the extended euclidian algorithm for polynomials works for a BCH code with coefficients from $GF(2^4)$ in https://en.wikipedia.org/wiki/BCH_code
for ...
- 315
-3
votes
0
answers
46
views
A property of the steps of Extended Euclidean Algorithm on Gaussian integers [duplicate]
Suppose that we have a computer program, if we give it two Gaussian integers $a, b (|a|>|b|>0)$, it will return three numbers $x,y,n$, where $x$ and $y$ are the Bezout coefficients produced by ...
- 49
0
votes
1
answer
27
views
Clarification on the forward extended Euclidean algorithm for finding gcd and linear solution [duplicate]
I have been reviewing Bill Dubuque's explanation of a forward version of the extended Euclidean algorithm in another question. I have seen other explanations of this method on the internet, but Bill's ...
- 99
0
votes
0
answers
36
views
Question about proof, using contrapositive, of Lamé’s theorem
Given the following lemma: If $a > b \geq 1$ and the call EUCLID(a, b) performs $k \geq 1$ recursive calls, then $a \geq F_{k+2}$ and $b \geq F_{k+1}$, which can be proved by induction, how is the ...
- 53
0
votes
1
answer
35
views
Euclidean algorithm in commutative rings with unity [duplicate]
Let R be a commutative ring with identity, and J an ideal generated by the members $a^n-1$ and $a^m-1$ for some $a \in R$ and $n, m$ positive integers.
I want to establish that the principal ideal ...
- 583
0
votes
1
answer
62
views
The state machine for "Extended Euclidean Gcd Algorithm" terminates after at most the same number of transitions as that of the Euclidean algorithm
This is one following question based on one question I asked before
In spring18 mcs.pdf, it has Problem 9.13:
Define the Pulverizer State machine to have:
$$
\begin{align*}
\text{states} ::=&...
- 416
0
votes
1
answer
58
views
Why is the Pulverizer machine partially correct?
In spring18 mcs.pdf, it has Problem 9.13:
Define the Pulverizer State machine to have:
$$
\begin{align*}
\text{states} ::=& \mathbb{N}^6&\\
\text{start state} ::=& (a, b, 0, 1, ...
- 416
-1
votes
1
answer
43
views
What have I missed here in this Euclidean algorithm trying to find D of RSA
Given the RSA public key find the decryption key d and decrypt the ciphertext c=8.
Known information:
n=119, p=17, q=7, e=13
$\phi(n) = (p-1)(q-1) = 16\times 6=96$
Equation for finding d:
$$ed\...
- 269
1
vote
1
answer
81
views
RSA finding D key
Given the RSA public key find the decryption key d and decrypt the ciphertext c=5.
Known information:
n=221, p=17, q=13, e=11
$\phi(n) = (p-1)(q-1) = 16\times 12=192$
Equation for finding d:
$$ed\...
- 269
-1
votes
4
answers
46
views
Use the Euclidean algorithm steps to find ALL the integer solutions of the equation [duplicate]
Use the Euclidean algorithm to find ALL the integer solutions of the equation:
$$5x+72y=1$$
My attempt:
$5x + 72y =1$
$72 = 14 \times 5 + 2 \quad (14~obtained~by~72/5 = 14.4)$
$5 = 2 \times 2 + 1$
...
- 269
4
votes
1
answer
111
views
Minimal size of $a^2+b^2$ such that $ad-bc=1$
If $c,d$ are two relatively prime positive integers, then we can find integers $a,b$ such that $ad-bc=1$. But $a$ and $b$ are not unique: we can replace $a$ with $a+kc$ and $b$ with $b+kd$ for any ...
- 1,136
4
votes
0
answers
99
views
Minimum $k$ for which every positive integer of the interval $(kn, (k+1)n)$ is divisible by at least one prime number less than $n$
As a continuation of this question relating the Minimum $k$ for which every positive integer of the interval $(kn, (k+1)n)$ is composite and this other one on the divisibility of numbers in intervals ...
- 1,190
1
vote
3
answers
308
views
About reversing the Euclidean Algorithm, Lemma of Bézout
From the book Discrete Mathematics for Computing 2nd Edition in eBook:
I know how to perform the Euclidean Algorithm and GCM(a,b). I am however, deeply confused by this:
$$1 = 415 - 69(421 - 1 \times ...
- 269