+0  
 
0
2835
6
avatar

(7*X)mod 26 =1

difficulty advanced
 May 4, 2015

Best Answer 

 #5
avatar+893 
+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.)

 May 8, 2015
 #1
avatar+29 
+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

 May 4, 2015
 #2
avatar+128055 
+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........

 

  

 May 4, 2015
 #3
avatar+118587 
+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.      :/

 May 5, 2015
 #4
avatar+118587 
+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?

 May 7, 2015
 #5
avatar+893 
+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
 #6
avatar+118587 
0

Thank you Bertie,    

It was good to see you back on the forum.  

I will look at your answer thoroughly but I have not done so yet :/

 May 9, 2015

4 Online Users

avatar