#5**+15 **

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.

If

$$\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.)

Bertie
May 8, 2015

#1**+5 **

If X must be a whole number:

Can't remember if there is a faster way, but you need to find a multiple of 26 that when 1 is added to it is a multiple of 7.

If X can be anything, fractional too, then X=27/7 is one such X

TheMathsStudent
May 4, 2015

#2**+5 **

Here's a pattern...

[11*26 + 1 ] / 7 = 41

[25*26 + 1] / 7 = 93

[39*26 + 1 ] / 7 = 145

[53*26 + 1 ] = 197

So....it appears that the pattern [(-3 ± 14n) *26 + 1 ] / 7 will produce an integer ....for n= 0, 1, 2, 3......

So "X" must be, in general, [41 ± 52k] for k = 0, 1, 2, 3........

CPhill
May 4, 2015

#3**+5 **

Thanks Chris and TheMathsStudent

I thought there was some definative way to do this.

$$\\7Xmod26=1\\\\

\frac{7x}{26}=N+\frac{1}{26} \qquad $Where X and N are both integers$\\\\

7X=26N+1$$

Multiples of 26 are 26,52,78, 104,130, 156, 182,

(Multiples of 26) +1 are 27,53,79, **105**, 105 = 7*15

**So X=15 works this is one solution**

7*15=26(N)+1 N=4

-----------------------------------------------------

$$\left({\mathtt{7}}{\mathtt{\,\times\,}}{\mathtt{15}}\right) {mod} \left({\mathtt{26}}\right) = {\mathtt{1}}$$

That is good ** X=15 is the smallest value of X**

--------------------------------------------------------

Now I want to find a general solution

If (7*15) mod 26=1

Then I think

(7*15+26G) mod 26 must also =1

Thinking, thinking. :/

Melody
May 5, 2015

#4**+5 **

okay, I am thinking here ....

if

7K mod 26=1

I know that k=15 is the smallest integer solution

so

(7*15) mod 26 =1

so

(7*15+26N) mod 26 =1

so

$$[7(15+\frac{26N}{7})]= 1$$ where N is an integer.

So **$$K=15+\frac{26N}{7}$$ is a general solutions**

**NOW Wolfram|Alpha gave the general solution as K=15+26N where K is an integer.**

But why did Wolfram|Alpha care about K being an integer?

I can see that N must be an integer, but why does K have to be an integer

**Would any other mathematician care to comment?**

Melody
May 7, 2015

#5**+15 **

Best Answer

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.

If

$$\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.)

Bertie
May 8, 2015