We use cookies to personalise content and advertisements and to analyse access to our website. Furthermore, our partners for online advertising receive pseudonymised information about your use of our website. cookie policy and privacy policy.


Questions 1
Answers 198


Unless we are told something to the contrary, unknowns in equations such as this are always assumed to be integers.


If  d is the greatest common divisor (gcd) of a and n, the linear congruence  

$$\displaystyle ax\equiv b \bmod n$$ 

has a solution only if b is also divisible by d and in that case there will be an infinite number of solutions given by

$$\displaystyle x=x_{0}+\frac{nt}{d},$$

where  $$x_{0}$$  is any solution whatever, and t is an integer, (positive or negative), or zero.

For the equation in question,

$$\displaystyle 7x = 1\bmod 26,\qquad d = 1,$$

so the general solution will be

$$\displaystyle x = x_{0}+\frac{26t}{1} = x_{0}+26t.$$

Finding a suitable  $$x_{0}$$  is a trial and error thing, run through the multiples of 7 and 26 looking for the first pair for which the multiple of 7 is 1 greater than the multiple of 26 That happens to be 15 and 4, so the general solution is

$$\displaystyle x = 15 + 26t, \quad t\:\in \:Z.$$ 


The result given earlier comes from the theory of linear Diophantine equations.


$$\displaystyle d = \gcd(a,b),$$

the equation

$$\displaystyle ax+by = c$$

has integer solutions only if c is also divisible by d, and in that case there will be an infinite number of solutions given by

$$\displaystyle x = x_{0}+\frac{bt}{d},\quad y=y_{0}-\frac{at}{d} \quad (t\: \in Z),$$

and where  $$\displaystyle \; x_{0},y_{0}$$  is any particular solution.

(For large values of a and b, $$\displaystyle \; x_{0},y_{0}$$  and d are usually found using Euclid's algorithm.)

( The equation

$$\displaystyle ax\equiv b \bmod n$$

is equivalent to

$$\displaystyle ax-b=kn \Rightarrow ax-kn=b,$$

which, with a change of letters and a change of sign, is the Diophantine equation above.)

May 8, 2015