Results 1 to 7 of 7

Math Help - Help with prime number and modulo

  1. #1
    Newbie
    Joined
    Jun 2010
    Posts
    4

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    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.
    Last edited by undefined; June 19th 2010 at 08:32 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by undefined View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    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

    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
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by Bacterius View Post
    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
    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Jun 2010
    Posts
    4
    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"
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    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

    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 ), you might appreciate to know that the probability of two random numbers being coprime is \frac{6}{\pi^2} ...
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. If a has order n - 1 modulo n, then n is prime.
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: November 10th 2011, 01:29 PM
  2. Summation up to p-1 modulo p, p prime
    Posted in the Number Theory Forum
    Replies: 17
    Last Post: October 21st 2011, 06:46 PM
  3. prime and modulo proofs
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: February 22nd 2011, 03:43 AM
  4. square modulo the prime...
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: April 12th 2010, 08:10 AM
  5. Order modulo a prime
    Posted in the Number Theory Forum
    Replies: 8
    Last Post: March 22nd 2010, 03:25 PM

Search Tags


/mathhelpforum @mathhelpforum