# 1 * 9 = 9 = 9

13»

• This is funny; I didn't know other people were into this. I did some work in college expanding the adding-digits trick to higher primes; basically, for every power of 10, you take the modulus against the prime under question. Eventually, you will find that there's some 10^x that is congruent to 1 mod \$prime_under_question. That'll be the end of your series (beginning of the next cycle, for pedants). Once you have the series, you can take a large number, multiply each digit by the terms in the series, and sum them to get your congruent number. Here's an example:

For 7, the series is 1,3,2,6,4,5. So to see if 5435235342 is divisble by 7, take the last six digits (six b/c that's how many terms are in our series), multiply them by their counter part in the series, and sum up those multiplications.

2 * 1 = 2
4 * 3 = 12
3 * 2 = 6
5 * 6 = 30
3 * 4 = 12
2 * 5 = 10
If you have more digits in your number than terms in your series (not raer), you just cycle through the series again.
5 * 1 = 5
3 * 3 = 9
4 * 2 = 8
5 * 6 = 30

2+12+6+40+12+10+5+9+8+30=124. So 5435235342 is congruent to 124 mod 7. This does not tell us directly whether or not 5435235342 is evenly divisible by 7, but it makes it much easier to answer, as 124 is guaranteed to have the same remainder as 5435235342 when divided by 7, because of our calculation (presuming I performed it correctly here). Of course, you can carry out the same process on 124:

4 * 1 = 4
2 * 3 = 6
1 * 2 = 2

4+6+2=12, which leaves a remainder of 5 when divided by 7. So, by calculating a simple series and performing some basic multiplication and arithmetic, we're able to say that 5435235342 / 7 = some integer with a remainder of 5, or that 7 is not a factor of 5435235342.

This is actually a very useful thing, to construct congruent numbers against arbitrary primes; it has applications for factoring large numbers, for example. You can also precalculate these series and store in a lookup table. Some of this math is easier to implement in hardware, as well.

• So, by calculating a simple series and performing some basic multiplication and arithmetic, we're able to say that 5435235342 / 7 = some integer with a remainder of 5, or that 7 is not a factor of 5435235342.

This is actually a very useful thing, to construct congruent numbers against arbitrary primes; it has applications for factoring large numbers, for example. 