Linked Questions

57
votes
7answers
8k views

Polynomial division: Is this trick obvious?

The following question was asked on a high school test, where the students were given a few minutes per question, at most: Given that, $$P(x)=x^{104}+x^{93}+x^{82}+x^{71}+1$$ and, $$Q(x)=x^4+...
16
votes
3answers
4k views

Solving linear congruences by hand: modular inverses, fractions

When I am faced with a simple linear congruence such as $$9x \equiv 7 \pmod{13}$$ and I am working without any calculating aid handy, I tend to do something like the following: "Notice" that adding $...
3
votes
2answers
5k views

How to find the numbers of Bezout identity for two numbers

I'm having troubles finding two numbers a,b such that $ 288a+177b=3=gcd(177,288) (1) $ I've been writing the equations of the Euclids algorithm one over another many times to get any pair that verify ...
1
vote
2answers
2k views

Troubles finding inverse modulus [duplicate]

Possible Duplicate: finding inverse of $x\\bmod y$ Hello all Me and some friends are studying for a discrete exam and we are having some troubles finding the inverse modulus of things. The ...
3
votes
2answers
2k views

Congruency and Congruent Classes

so studying for my midterm on Tuesday (intro to abstract algebra). The topics on the exam are Division Algorithm, Divisibility, Prime Numbers, FTA, Congruency, Congruent Classes and very brief ...
2
votes
1answer
1k views

General method for solving $ax\equiv b\pmod {n}$ without using extended Euclidean algorithm?

Consider the linear congruence equation $$ax\equiv b\pmod { n}.$$ One way to solve it is solving a linear Diophantine equation $$ ax+ny=b. $$ I saw somebody solved it by another method somewhere I ...
2
votes
2answers
726 views

Can Euclid's Division Algorithm and/or Fundamental Theorem of Arithmetic implies this property of prime numbers

There is an exercise on page 44 of Amann's book Analysis, Vol I which stuck me so much. I quoted it here: Ex7: Let $p\in\mathbb{N}$ with $p>1.$ Prove that $p$ is a prime number if and only if, ...
4
votes
2answers
420 views

'Gauss's Algorithm' for computing modular fractions and inverses

There is an answer on the site for solving simple linear congruences via so called 'Gauss's Algorithm' presented in a fractional form. Answer was given by Bill Dubuque and it was said that the ...
1
vote
3answers
280 views

Using Fermat's Little Theorem or Euler's Theorem to find the Multiplicative Inverse — Need some help understanding the solutions here.

The answers to multiplicative inverses modulo a prime can be found without using the extended Euclidean algorithm. a. $8^{-1}\bmod17=8^{17-2}\bmod17=8^{15}\bmod17=15\bmod17$ b. $5^{-1}\bmod23=5^{...
1
vote
2answers
508 views

using Gauss' algorithm (for linear congruences) for A > B

To solve $Bx \equiv A \pmod{m}$, use Gauss' algorithm. The algorithm works perfectly when $A < B$. For example, to solve $6x \equiv 5 \pmod{11}$: $$x \equiv \frac{5}{6} \equiv \frac{5(2)}{6(2)} \...
5
votes
1answer
104 views

Iterations of modulus operation

While working on a completely unrelated task, I thought up the following problem: Consider the following process. Let $a_0$ and $n$ be given, and determine $a_1,\ldots, a_k$ as follows: $$a_{j+1}...
0
votes
2answers
280 views

Euclid proof explanation

Can anyone help me understand the following proof that if $p|ab$ then $p|a$ or $p|b$? This proof is on a separate question. Suppose there were a counterexample, with $pa=bc$, $p$ a prime, but ...
-1
votes
3answers
95 views

Find $a \in \mathbb Z$, which solves $11 \cdot a \equiv 1 \pmod {1247}$

How would you solve the question (in the title)? Can I apply your approach/solution (for the title question) also for: $13 \cdot a \equiv 1 \pmod {1337}$ and $69 \cdot a \equiv 8 \pmod {8008}$ etc.?
1
vote
0answers
53 views

Solving linear congruences and multiplicative inverses

Inspired by Bill Dubuque's Gauss Algorithm I have been interested in finding such optimal ways of solving simple linear congruences and finding multiplicative inverses. Bill presented the algorithm ...
0
votes
0answers
46 views

Euclidean algorithm variant

Normal Euclidean algorithm iterates $(a$ mod $b, b)$ for $a>b$. I have noticed that iterating $(a$ mod $ b, a)$ (keeping the $a$ fixed through descent) will also give the GCD. Can anyone show why ...