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

Expand Messages
• 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.