# Running a loop to check for multiple congruences

I have the code for a loop to run. Right now it can check if a number is a square and at the same time check if it is congruent 0 mod 47. My questions is, how can I alter the code to see if it is congruent for more than one prime. SO for instance I would like it to check that a number is congruent, 0 mod 5, 0 mod 13 and 0 mod 17 all at once and only keep or print the numbers which are. I would try something like: 'Select[Range[10^7]^2, Divisible[7 # + 4, 5], Divisible[7 # + 4, 13], Divisible[7 # + 4, 17] &]' but it just prints numbers most of which I am assuming do not satisfy the desired effect

• Select[Range[10^5]^2, Divisible[#, 5] && Divisible[#, 13] && Divisible[#, 17] &]? – Henrik Schumacher Mar 20 at 23:14
• also I would really like to be able to check whether (4^n)-1 is congruent 0 mod5 0 mod 13 and 0 mod 17 not for 7n+4 – argamon Mar 20 at 23:15
• thank you @HenrikSchumacher, I actually do not care if the number is a perfect square rather it must have the form (4^n)-1. I apologize for my ignorance but your help is greatly appreciated – argamon Mar 20 at 23:17
• Well, I don't see any problem here. You already found that you may use Select. The only thing you did wrong is not to use And (&&). The selection function is required to produce either True or False. And, of course, you may use any list you like as first argument of Select. – Henrik Schumacher Mar 20 at 23:21

To find solutions, for example, the code:

FindInstance[{n == a^2, 7 n + 4 == m, m == 5 b}, {n, m, a, b}, Integers]


returns {} to indicate no solutions. The alternative code

Reduce[{n == a^2, 7 n + 4 == m, m == 5 b}, {m}, Integers]


returns False similarly. Try variations of these codes depending on your needs.

However, both Reduce[] and FindInstance[] are not good with exponential equations.

For that, you can use some code

Select[2^Range[0, 20] - 1, Divisible[#, 5] && Divisible[#, 13] &]


which returns {0, 4095} and you can try variations of this.

• Thank you, I just want to adjust it so that it does it for numbers of the form (4^n)-1 so I tried the following code and it does nothing: – argamon Mar 20 at 23:29
• Select[Table[Divisible[(4^i)-1,5] && Divisible [(4^i)-1, 13] && Divisible[(4^i)-1,17] {i,200} &] – argamon Mar 20 at 23:29
• That is helpful but how could I use that to check for it being divisible by 5 and 13 and 17 at the same time or if I change the base 4 to 3 lets say? – argamon Mar 20 at 23:49
• I tried adjusting the base and it tells me that everything is zero: – argamon Mar 20 at 23:51
• {In:= FindInstance[{2^i-1 == n, n == 5 a}, {i, a, n}, Integers] Out= {{i -> 0, a -> 0, n -> 0}} – argamon Mar 20 at 23:51

For the question, expressed in a comment by argamon, of finding numbers of the form (4^n)-1 congruent to 0 mod 5, 0 mod 13, and 0 mod 17, please consider the function ChineseRemainder.

Block[{c},
Flatten[Table[
c = ChineseRemainder[{0, 0, 0}, {5, 13, 17}, m];
If[c == m, m, {}],
{m, Table[4^k - 1, {k, 1, 50}]}]]
]


{16777215, 281474976710655, 4722366482869645213695, 79228162514264337593543950335}