Loading ...
Sorry, an error occurred while loading the content.
 

Number of solutions to B = nx + my, B prime and (n,m) = 1

Expand Messages
  • Mark Underwood
    How many positive, non zero integer solutions are there to the equation B = nx + my given any prime B and any (n,m) = 1 ? It turns out to be easy despite my
    Message 1 of 1 , Jul 27, 2003
      How many positive, non zero integer solutions are there to the
      equation

      B = nx + my

      given any prime B and any (n,m) = 1 ?

      It turns out to be easy despite my taking days to figure it out by
      looking at reams of data! The result is of course probably old hat to
      number theorists out there. I'm posting it here even though it turns
      out that B doesn't have to be prime (egad!) for the relation to work.

      First, let

      b = B mod (n*m)

      Thus b is less than n*m. As it happens, b = nx + my has exactly one
      solution or no solution. (See note at the end for another
      interesting observation regarding this.)

      If b = nx + my has no solution, the number of positive non zero
      solutions to (B = nx + my) simply is :

      (B - b)/(n*m)

      If b = nx + my has a solution, the number of positive non zero
      solutions to (B = nx + my) simply is :

      (B - b)/(n*m) + 1

      I have little idea if the above is useful at all, but it clarified
      something which I was very nebulous about!

      Mark


      (Note: If b = nx + my has no solution, then b's mirror number
      (n*m - b) will have a solution, and visa versa. This means that given
      any n and m relatively prime, the number of b's from 1 up to n*m - 1
      which have a solution is equal to the number of b's that don't have a
      solution. )
    Your message has been successfully submitted and would be delivered to recipients shortly.