# 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] &]? Commented Mar 20, 2019 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 Commented Mar 20, 2019 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 Commented Mar 20, 2019 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. Commented Mar 20, 2019 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: Commented Mar 20, 2019 at 23:29
• Select[Table[Divisible[(4^i)-1,5] && Divisible [(4^i)-1, 13] && Divisible[(4^i)-1,17] {i,200} &] Commented Mar 20, 2019 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? Commented Mar 20, 2019 at 23:49
• I tried adjusting the base and it tells me that everything is zero: Commented Mar 20, 2019 at 23:51
• {In[3]:= FindInstance[{2^i-1 == n, n == 5 a}, {i, a, n}, Integers] Out[3]= {{i -> 0, a -> 0, n -> 0}} Commented Mar 20, 2019 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}