+0  
 
0
484
6
avatar

(7*X)mod 26 =1

difficulty advanced
Guest May 4, 2015

Best Answer 

 #5
avatar+889 
+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
Sort: 

6+0 Answers

 #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

TheMathsStudent  May 4, 2015
 #2
avatar+78577 
+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
avatar+90988 
+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
avatar+90988 
+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
avatar+889 
+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+90988 
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 :/

Melody  May 9, 2015

4 Online Users

We use cookies to personalise content and ads, to provide social media features and to analyse our traffic. We also share information about your use of our site with our social media, advertising and analytics partners.  See details