Help with prime number and modulo

Printable View

June 19th 2010, 05:51 PM
chauhan

Help with prime number and modulo

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.
June 19th 2010, 07:17 PM
undefined

So we're using that

$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:

$\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 $A^X + B^Y \equiv C^Z\ (\text{mod}\ N)$ then we cannot conclude whether or not $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 $\gcd(A,N) = \gcd(B,N) = \gcd(C,N) = 1$ . I think we want this because: consider the set $S=\{A^1, A^2, ..., A^{N-1}\}$ . If $\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.
June 19th 2010, 07:44 PM
chiph588@

Quote:

Originally Posted by undefined

So we're using that

$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:

$\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 $A^X + B^Y \equiv C^Z\ (\text{mod}\ N)$ then we cannot conclude whether or not $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 $\gcd(A,N) = \gcd(B,N) = \gcd(C,N) = 1$ . I think we want this because: consider the set $S=\{A^1, A^2, ..., A^{N-1}\}$ . If $\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 $N$ , it may be very hard to know whether $N$ is prime or not.
June 19th 2010, 08:03 PM
Bacterius

Quote:

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 $\zeta({2})^{-1} = \frac{6}{\pi^2} \approx 0.608$
June 19th 2010, 08:12 PM
chiph588@

Quote:

Originally Posted by Bacterius

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!

Quote:

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.
July 12th 2010, 09:00 PM
chauhan

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"
July 12th 2010, 11:10 PM
Bacterius

Quote:

Tell that to the people of GIMPS!

Ah, I thought you were simply talking about *huge* numbers ( $10^{10000}$ ), not *huge huge* numbers ( $10^{10000000}$ ). Well I guess even polynomial time algorithms have their limits xD

Quote:

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)

Quote:

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 $\frac{6}{\pi^2}$ ...