Help with prime number and modulo

Jun 2010
4
0
Hi,
I have a question about performing a modulo with large prime numbers.
If I want to check if A^X + B^Y = C^Z, I was told to try the following filtering method:
(A^XmodN + B^YmodN)modN = C^ZmodN with two large values of N that are prime.
I dont understand the significance of the values of N being prime. Apparently this causes it to be a better filter than with values of N that are not prime.
Why is that? I only have very basic Math knowledge so please try and help me out.
 

undefined

MHF Hall of Honor
Mar 2010
2,340
821
Chicago
So we're using that

\(\displaystyle A^X + B^Y = C^Z \Rightarrow A^X + B^Y \equiv C^Z\ (\text{mod}\ N)\ \forall N\in\mathbb{Z},N>0\)

The contrapositive yields the test:

\(\displaystyle \text{Let}\ N\in\mathbb{Z},N>0\text{. Then}\ A^X + B^Y \not\equiv C^Z\ (\text{mod}\ N) \Rightarrow A^X + B^Y \ne C^Z\)

Of course, if we find that \(\displaystyle A^X + B^Y \equiv C^Z\ (\text{mod}\ N)\) then we cannot conclude whether or not \(\displaystyle A^X + B^Y = C^Z\).

I'm guessing that A,B,C are small enough such that "N is large" means N is greater than A,B,C. This would mean that choosing N prime implies \(\displaystyle \gcd(A,N) = \gcd(B,N) = \gcd(C,N) = 1\). I think we want this because: consider the set \(\displaystyle S=\{A^1, A^2, ..., A^{N-1}\}\). If \(\displaystyle \gcd(A,N) \ne 1\) then there must be duplicates in S mod N. The number of distinct elements of S is maximized (probabilistically) for N prime. See A046144 at OEIS; the sequence is the number of primitive roots of n. So thinking in terms of probability, choosing N prime basically increases the population size, thus giving lower probability that two randomly chosen elements add to a third element, thus giving higher probability that the test will successfully weed out false equations.

Anyone else care to validate my reasoning? I'm a little unsure.
 
Last edited:

[email protected]

MHF Hall of Honor
Sep 2008
1,163
429
Champaign, Illinois
So we're using that

\(\displaystyle A^X + B^Y = C^Z \Rightarrow A^X + B^Y \equiv C^Z\ (\text{mod}\ N)\ \forall N\in\mathbb{Z},N>0\)

The contrapositive yields the test:

\(\displaystyle \text{Let}\ N\in\mathbb{Z},N>0\text{. Then}\ A^X + B^Y \not\equiv C^Z\ (\text{mod}\ N) \Rightarrow A^X + B^Y \ne C^Z\)

Of course, if we find that \(\displaystyle A^X + B^Y \equiv C^Z\ (\text{mod}\ N)\) then we cannot conclude whether or not \(\displaystyle A^X + B^Y = C^Z\).

I'm guessing that A,B,C are small enough such that "N is large" means N is greater than A,B,C. This would mean that choosing N prime implies \(\displaystyle \gcd(A,N) = \gcd(B,N) = \gcd(C,N) = 1\). I think we want this because: consider the set \(\displaystyle S=\{A^1, A^2, ..., A^{N-1}\}\). If \(\displaystyle \gcd(A,N) \ne 1\) then there must be duplicates in S mod N. The number of distinct elements of S is maximized (probabilistically) for N prime. See A046144 at OEIS; the sequence is the number of primitive roots of n. So thinking in terms of probability, choosing N prime basically increases the population size, thus giving lower probability that two randomly chosen elements add to a third element, thus giving higher probability that the test will successfully weed out false equations.

Anyone else care to validate my reasoning? I'm a little unsure.
Perhaps it helps with redundancies.

For instance, it's redundant to check modulo 4 and modulo 2. So sticking with prime number prevents this. So given this and the fact that one can build to mod a composite via CRT, I think it's probably best to check modulo primes.

However if we're dealing with large \(\displaystyle N \), it may be very hard to know whether \(\displaystyle N \) is prime or not.
 
Nov 2009
927
260
Wellington
However if we're dealing with large N, it may be very hard to know whether is prime or not.
Fortunately this issue has been resolved. Just throw in a well-optimized Miller-Rabin test and you won't spend the year checking that number (Lipssealed)

I may be saying something stupid, but would it be possible, once the congruences have been established, to use the greatest common divisor function to ensure that the numbers aren't just congruent to the numbers but are equal to the numbers ? Then it would be certain that the original equation holds.
Just an idea ...

If this helps, note that the probability that two randomly picked numbers are coprime is \(\displaystyle \zeta({2})^{-1} = \frac{6}{\pi^2} \approx 0.608\)
 

[email protected]

MHF Hall of Honor
Sep 2008
1,163
429
Champaign, Illinois
Fortunately this issue has been resolved. Just throw in a well-optimized Miller-Rabin test and you won't spend the year checking that number (Lipssealed)
Tell that to the people of GIMPS!

I may be saying something stupid, but would it be possible, once the congruences have been established, to use the greatest common divisor function to ensure that the numbers aren't just congruent to the numbers but are equal to the numbers ? Then it would be certain that the original equation holds.
Just an idea ...
Having a solution to an equation modulo some number implies there is a solution over the integers too.
 
Jun 2010
4
0
But the point was that the modulo when performed twice successively with 2 numbers would only benefit with prime numbers. If the modulo is performed with just 1 number, it does not matter if the number is prime or not - just a large number would do... this is what my professor told me.... and he said "find out why"
 
Nov 2009
927
260
Wellington
Tell that to the people of GIMPS!
Ah, I thought you were simply talking about *huge* numbers (\(\displaystyle 10^{10000}\)), not *huge huge* numbers (\(\displaystyle 10^{10000000}\)). Well I guess even polynomial time algorithms have their limits xD

But the point was that the modulo when performed twice successively with 2 numbers would only benefit with prime numbers.
Actually it only benefits if it is performed with two coprime numbers (two prime numbers fullfill this requirement but 4 and 5 would be fine as well in a simpler context)

If the modulo is performed with just 1 number, it does not matter if the number is prime or not - just a large number would do...
Well as I pointed out, the two numbers have to be coprime with each other ... if one number is omitted then what has the remaining one to be coprime to ? This requirement falls with the removal of the second number and you are good to go. (actually, assume the removed number is equal to 1, which gives the same results, any number being coprime to 1).

All right this may not be true but I feel it looks good and often this coprime stuff is quite instinctive and reveals to be true at the end ... my apologies if I failed to grasp the actual problem. Also, if what I said turns out to be true (hopefully (Lipssealed)), you might appreciate to know that the probability of two random numbers being coprime is \(\displaystyle \frac{6}{\pi^2}\) ...