0

Pardon me if I haven't used correct algebraic terms.

a, b, c=> integer constants

x, y => +ve / -ve integers (Any one can be zero)

$\ (ax + by) \% 360 = c $

For eg: $\ (100x + 10y) \% 360 = 50 $

Is there a way by which we can determine whether a equation of the above given form be solved, satisfying the condition of x , y?

MeetM
  • 103
  • This is the third question we've receievd in the past hour on modular angle arithemetic, see here and here for the prior two closely related questions. What is the source of this question? Did you ask the prior two questions? Please tell use how much number theory you know. – Bill Dubuque Mar 15 '14 at 19:32
  • @BillDubuque The source is a programming question asked in contest on hackerearth.com. Its closed now. So no link :/ And no, I didn't ask the prior two questions. And I also think that the prior two questions asked are incorrect in relation with the problem that was asked. And looking at the answers I feel I really don't know much about number theory and linear congruence. Have to study alot! – MeetM Mar 15 '14 at 20:42

1 Answers1

1

This is true if and only if $100x + 10y$ and $50$ have the same remainder modulo $360$, i.e. $$ 100x + 10y \equiv 50 \pmod{360} $$ We can divide equations like this by any common factor, $$ 10x + y \equiv 5 \pmod{36} $$ One could solve this by Chinese remainder theorem. However, in this case it's simpler to note that $x$ can be anything, and $y$ is a function of $x$ $y = 5 - 10x$ (plus any multiple of $36$). So the solution to your equation is that $x$ is any integer, and $$ y = 5 - 10x + 36k $$ for any integer $k$. I.e., for any integers $x$ and $k$ you have the solution $(x, 5 - 10x + 36k)$.

Edit

In general, suppose $a,b,c,d$ are given, and we want to decide if the following equation has a solution: $$ ax + by \equiv c \pmod{d} $$

The set of possible values of $ax + by$, by Bezout's identity, is just the set of all multiples of $\gcd(a,b)$. In otherwise, this has a solution if and only if $$ k \gcd(a,b) = c \pmod{d} $$

has a solution for some $k$. But this equation is well-known (you can probably find many questions about it on this site). It has a solution if and only if $\gcd(\gcd(a,b), d)$ divides $c$ (source).

TL;DR: $\boldsymbol{ax + by \equiv c \pmod{d}}$ has a solution if and only if $\boldsymbol{\gcd(a,b,d)}$ divides $\boldsymbol{c}$. (This is the more mathematical way of stating your problem $(ax + by) \% d = c$.)

In this particular case, $\gcd(100, 10,50) = 10$, which does indeed divide $50$, so there is a solution.

Caleb Stanford
  • 45,895
  • Thanks @Goos! But can we in some way verify whether a solution exists or not...without trying every possible values of x and k till we get solution? – MeetM Mar 15 '14 at 20:45
  • @MeetM In this case every $x$ and $k$ gives you a solution. So you don't have try every possible one to know that a solution exists. – Caleb Stanford Mar 15 '14 at 21:08