Short method for computing this?

[mohamed el teir]

suppose a side of an equation : 26q+1 , and i want the least positive integer value for q that makes this side of equation divisible by 7, is there any short method to do this ?

 

[Merlin3189]

I don't know any short method, but you can work in mod 7.

So for eg. if 11x + 8 is divisible by 5, then in mod 5
11x + 8 = 0
10x + x + 8 = 0
0 + x + 8 = 0
x + 3 + 5 = 0
x + 3 + 0 = 0
So x is 2, 7, 12, etc.

Ed: just noticed this is too simple. So 13x +9 is divisible by 5. In mod 5,
13x + 9 = 0
3x + 4 = 0
3x = -4
3x = 1
so 3x = 6, 11, 16, 21, 26, 31, 36, etc
so x= 2, 7, 12, etc.

 

[mohamed el teir]

I don't know any short method, but you can work in mod 7.

So for eg. if 11x + 8 is divisible by 5, then in mod 5
11x + 8 = 0
10x + x + 8 = 0
0 + x + 8 = 0
x + 3 + 5 = 0
x + 3 + 0 = 0
So x is 2, 7, 12, etc.

Ed: just noticed this is too simple. So 13x +9 is divisible by 5. In mod 5,
13x + 9 = 0
3x + 4 = 0
3x = -4
3x = 1
so 3x = 6, 11, 16, 21, 26, 31, 36, etc
so x= 2, 7, 12, etc.

but when working with higher mod like mod 26 would this way be efficient ? for example when 9x-1 is divisible by 26

 

[Merlin3189]

No, I don't know how to make that simpler. Perhaps if you search on Diophantine equations, you can find something to help.

AFAIK
9x-1 = 0 (Mod 26)
then 9x= 1 is as far as I can get.
So 9x = 1, 27, 53, 79, 105,... The only way I can see to help now, is to look at these Mod 9
(so 0 = 1, 0, 8, 7, 6, 5, 4, 3, 2, 1, 0, ..) so the second term is the first that is not false
so 9x = second term = first term + 1 x 26 = 1 + 1*26 = 27
so x= 3
Check 9 x 3 - 1 = 27 -1 =26

That was a bit too easy,
so try 9x -17 = 0 (Mod 26)
then 9x = 17
So 9x = 17, 43, 69, ...
now to looking at these Mod 9
(so 0 = 8, 7, 6, 5, 4, 3, 2, 1, 0, .. ) so the 9th term is the first that is not false
so 9x = 9th term = first term + 8 x 26 = 17 + 8*26 = 225
so x= 25
(Check 9 x 25 - 17 = 225 -17 = 208 = 26 x 8 )

It actually looks as if you could simplify the Mod 9 step, but in some cases the change in mod base does not give such a simple sequence.

 

[Svein]

A short trip into Excel gave q=4 (next one is 11, then 18 , 25).

 

[Merlin3189]

A short trip into Excel gave q=4 (next one is 11, then 18 , 25).

But what method did you use in Excel?

 

[Svein]

Brute force - I created the series 0, 1, 2... 29 in column B, 26*B_n + 1 in column C and Mod(C_n, 7) in column D. Then I just looked for 0 in column D.
(
0 1 1
1 27 6
2 53 4
3 79 2
4 105 0
5 131 5
6 157 3
7 183 1
8 209 6
9 235 4
10 261 2
11 287 0
12 313 5
13 339 3
14 365 1
15 391 6
16 417 4
17 443 2
18 469 0
19 495 5
20 521 3
21 547 1
22 573 6
23 599 4
24 625 2
25 651 0
26 677 5
27 703 3
28 729 1
29 755 6)