Intereting Posts

The smallest integer whose digit sum is larger than that of its cube?
Etymology of $\arccos$, $\arcsin$ & $\arctan$?
Cardinality of the Irrationals
Is there a name for the sum of increasing powers?
An inequality on the root of matrix products (part 2 – the reverse case)
Function that sends $1,2,3,4$ to $0,1,1,0$ respectively
Is there a name for this strange solution to a quadratic equation involving a square root?
Power of a matrix, given its jordan form
Examples of comma categories
Why does the volume of a hypersphere decrease in higher dimensions?
Ellipse in polar coordinates
Finding integers satisfying $m^2 – n^2 = 1111$
Is there an everywhere discontinuous increasing function?
Trigonometric/polynomial equations and the algebraic nature of trig functions
Isometries of the sphere $\mathbb{S}^{n}$

**Question**: How can I solve: $min\{x \in \mathbb N_0 \quad |x \cdot 714 \equiv 1292 \mod 1972 \} $ ?

I only know about:

$x \cdot a \equiv _m b \Rightarrow m|x \cdot a – b$

- A variant of the Knight's tour problem
- Solve $x^2$ $mod$ $23 = 7^2$
- Finding a generating function of a series
- Looking for induction problems that are not formula-based
- Induction proof (bitstring length)
- Proving Set Operations

different way of notation:

$min\{x \in \mathbb N_0 \quad | x \cdot 714 \equiv_{1972} 1292\}$

How to go on?

I appreciate every hint.

- Decomposing a discrete signal into a sum of rectangle functions
- Lights out game on hexagonal grid
- This sigma to binom?
- Polynomial Question
- Sum of cubes proof
- Can you draw the e-NFA from the following definition?
- Solve $x^2$ $mod$ $23 = 7^2$
- Vertical bar sign in Discrete mathematics
- Asymptotics for a partial sum of binomial coefficients
- Expressing a positive integer as a sum of positive integers

As $714=34\cdot21$, $1292=34\cdot 38$, $1972=34\cdot 58$, this is equivalent to solving $21 x\equiv 38\mod 58$.

We have to find the inverse of $21$ modulo $58$. The tool for this is the *Extended Euclidean algorithm*:

$$\begin{array}{rrrl}

\hline

r_i&u_i&v_i&q_i\\

\hline

58&0&1\\

21&1&0&2\\

\hline

16&-2&1&1\\

5&3&-1&3\\1&-11&4\\

\hline

\end{array}$$

Thus the inverse of $21$ mod $58$ is $-11\equiv47$. The solution is

$$x\equiv47\cdot 38\equiv (-11)(-20)\equiv 46\mod 58. $$

Let’s say you want to solve $ax \equiv b \mod{m}$. If $gcd(a,m)=1$, then there is a unique solution. (You should be able to get this solution)

Now if $gcd(a,m) = d$, then solution exists iff $b$ divides $d$. You should try to reduce this to a equation between $\frac{a}{d}, \frac{b}{d} $ and $\frac{m}{d}$. From this solution , you will get mutiple solutions for the initial equation. Can you easily find the min of that?

Further hint for the reduction – Solving $ax \equiv b \mod{m}$ is same as solving $ax = b + my$.

- Does Lowenheim-Skolem theorem depend on axiom of choice?
- Another quadratic Diophantine equation: How do I proceed?
- Compute the Jacobson radical of the group ring $\mathbb{F}_2S_3$.
- How to Double integrals
- How many elements in a number field of a given norm?
- Proof by the substitution method that if $T(n) = T(n – 1) + \Theta(n)$ then $T(n)=\Theta(n^2)$
- Is 1 divided by 3 equal to 0.333…?
- A semigroup $X$ is a group iff for every $g\in X$, $\exists! x\in X$ such that $gxg = g$
- How do you read the symbol “$\in$”?
- What exactly does $\frac{dx}{dy}$ mean?
- Elementary proof for: If x is a quadratic residue mod p, then it is a quadratic residue mod p^k
- What does $\propto$ mean?
- Cryptography and Coding Theory
- How to solve infinite repeating exponents
- Many other solutions of the Cauchy's Functional Equation