0

I've got $$a = bx + y \pmod n$$ I tried to alter it to $$a = y/b + x \pmod n$$

But I don't think that works. If I can't do that, then can I turn it into anything where $a$ is equal to $x$ + or - something? I'm looking for an answer to this such that $x$ is not multiplied or divided by anything. Addition and subtraction are fine.

Mine
  • 127
  • In order to so called "divide" by $b$, you need $b$ to be invertible modulo $n$. Said differently, you need $\gcd(b,n)=1$. – Anurag A Sep 06 '17 at 04:15
  • I'm not worried about modular inverses, I'm concerned about it being mathematically sound. I'm not sure I can move the variables around legitimately to produce the desired result or anything similar to it. – Mine Sep 06 '17 at 04:23
  • 1
    Why would you even think that $b x + y$ and $-y/b + x$ were the same (with or without the $\mod n$)? Have you tried any example? – Robert Israel Sep 06 '17 at 05:23
  • Its not exactly what I got, all I'm looking for is something similar to it. anything that has "a = x +/-" something. – Mine Sep 06 '17 at 05:26
  • You already know what $a$ is congruent to mod $n$, namely $b x + y$. Well, you could call that $x + (b-1) x + y$, but it certainly won't be $x + $ (something that doesn't depend on $x$) unless $b = 1 (\text{mod}; n)$. Why should it be? – Robert Israel Sep 06 '17 at 05:29
  • Why shouldn't it be? ;) I'm not saying there's a sound solution either. Perhaps the correct answer is that there is no answer that fits. That is entirely possible. But even that can facilitate knowledge and understanding. – Mine Sep 06 '17 at 05:32
  • I think i got it wrong, but this was my thought $a=bx+y$ yields $0=bx+y-a$ which yields $-y=bx-a$ which yields $-y/b=x-a$, which yields $-y/b-x=-a$ which would yield $y/b + x = a$, but I think I didn't move the b over properly. – Mine Sep 06 '17 at 05:39
  • 1
    Why do you say $-y = bx-a$ yields $-y/b = x - a$? Surely, you can see that is dead wrong? You can't divide the -y, and the bx by b but refuse to divide the $a$ by $b$. If anything gets divided by $b$ then everything must be divided by $b$. – fleablood Sep 06 '17 at 06:34
  • @fleablood that's why I'm here, because that didn't seem right. I've merely showed you what I had so far so you knew what I had tried. – Mine Sep 06 '17 at 06:39
  • @RobertIsrael Not true, it can also hold for $,b\not\equiv 1\pmod{!n},$ when $n$ is composite - see my answer. – Bill Dubuque Sep 06 '17 at 14:38

3 Answers3

2

Your implication holds only for special values of $\,a,b\pmod{\!n},\,$ namely those satisfying $\,ab\equiv a.\,$ Indeed, assuming $\,b\,$ is invertible $\!\bmod n\,$ (so your $\,y/b \equiv yb^{-1}$ uniquely exists), then we have

Theorem $\,\ \ (a\equiv bx+y \,\Rightarrow\, a \equiv x+y/b) \iff ab\equiv a\,\ \pmod{\!n}$

Proof $\ \ (\Rightarrow)\ \ \ 0\equiv a\! -\! a\equiv (b\!-\!1)(x+y/b)\equiv (b\!-\!1)a\,\Rightarrow\, ab\equiv a$

$(\Leftarrow)\ \ \ ab\equiv a\,\Rightarrow a\equiv ab^{-1}\,$ so $\,\ b^{-1}\,(a\equiv bx+y)\ \Rightarrow\ a\equiv x+y/b$

Remark $\ ab\equiv a\pmod{n}\,$ has nontrivial solutions $\,a\not\equiv0,\,b\not\equiv 1$ precisely when $\,n\,$ is composite, and these solutions correspond to nontrivial factorizations of $\,n.\,$ Indeed by unique prime factorization $\,ab\equiv a\pmod{n}\iff n\mid (a\!-\!1)b\iff n = cd,\ c\mid a\!-\!1,\ d\mid b.\,$

Bill Dubuque
  • 272,048
1

If $b$ and $n$ are relatively prime, there is a $m$ such that $mb =1 \pmod n $.

Then, multiplying $a = bx + y \pmod n $ by $m$ we get $am = bmx + ym \pmod n = x + ym \pmod n $ which can also be written $a/b = x + y/b \pmod n $.

marty cohen
  • 107,799
  • is it possible to get that a by itself too? I understand that may not be possible, but that's why I'm asking; I don't know. – Mine Sep 06 '17 at 06:15
  • Um, you do realize that $y = bx - a$ means $\frac yb = \frac{bx -a}b = x - \frac ab \ne x -a$, don't you? Of course you can not divide everything else by $b$ and not divide the $a$ by $b$. – fleablood Sep 06 '17 at 06:30
  • Hence my dilemma regarding what I want and what is possible and why I posted the question. I posted the question because I thought that didn't make sense. It wasn't a belief that the $b$ could be feasibly be divided as I showed that led me here to ask my question. It was my belief that it wasn't feasible to do that that led me to ask the question. It seems as though there is no feasible solution to my goal. – Mine Sep 06 '17 at 06:36
  • The basic idea is that, for integers n and b, there is an inverse for b mod n if and only if n and b are relatively prime. That is when you can divide by b mod n (and divide by n mod b). – marty cohen Sep 06 '17 at 21:14
0

I think i got it wrong, but this was my thought a=bx+y yields 0=bx+y−a which yields −y=bx−a which yields −y/b=x−a, which yields −y/b−x=−a which would yield y/b+x=a, but I think I didn't move the b over properly.

Um $-y = bx -a$ does not yield $-\frac yb = x - a$. It yields $-\frac yb = x - \frac ab$.

And yes, you can do

$y \equiv bx + a \mod p \implies$

$\frac yb \equiv x + \frac ab \mod p$.

IF $\gcd(b,p) = 1$.

If $\gcd (b,p) = 1$ there are $m,n$ so that $1 = mb + np$ to $mb \equiv 1\mod p$. So we can right $\frac 1b \equiv m \mod p$.

But we can only write $\frac yb \equiv x + \frac ab \mod p$ if $y$ and $a$ are both multiples of $\gcd(b,p)$.

=====

Well you can have $an \equiv am \mod ap; a \ne 0$ would mean $n \equiv m \mod p$.

And $an \equiv am \mod p$ would mean $\frac {a}{\gcd(a,p)}m \equiv {a}{\gcd(a,p)}n \mod {p}{\gcd(a,p)}$ which means if $\gcd(a,p) = 1$ then $am \equiv an \mod p $ would mean $m \equiv n \mod p$.

The notation $\frac yb \equiv x \mod p$ is indeed a valid notation if it is true that $y \equiv bx \mod p$

So a class $x \equiv \frac yb \mod p$ will exist if and only if $y$ is a multiple of $\gcd(b,p)$

In particular if $p$ is prime and $k\not \equiv 0 \mod p$ then $\frac 1k \equiv x\mod p$ so that $xk \equiv 1 \mod p$ always exists.

But as to your actual question: Can you rewrite $a \equiv bx + y \mod n$ and $a \equiv x + \frac yb \mod n$. Um, I have no idea why you'd think you can just divide one side by $b$.

fleablood
  • 124,253
  • I didn't say I thought I could divide only one side by b. My comments show the steps I suggested, so I don't know where you're getting that. What I seek may not be feasible. – Mine Sep 06 '17 at 06:08
  • What you seek is feasable if $b$ and $p$ are relatively prime. Or if $y$ and $a$ are both multiples of the greatest common divisor of $b$ and $p$. – fleablood Sep 06 '17 at 06:28
  • But in your example, you still don't have $a$ by itself. Your pointing out that the $b$ doesn't move over as I suggested it doesn't proves you and I are at the same point in the understanding at this point in time. I'm still left with trying to figure out how to convert this equation into $a = x +/-$. Modular inverses aren't a concern. I understand your end equation could also be written as $y * b ^ -1 = x + a * b ^ -1$ and that's fine as is, but still doesn't have the $a$ by itself. – Mine Sep 06 '17 at 06:32
  • Um... have you never heard of the distributive law?????? Of course, you can't get $a$ by itself! Why should you? That would just be making up numbers. You might as well so $a = 27$ because that is the answer you want. – fleablood Sep 06 '17 at 06:40
  • Wow, touchy touchy. No, I've never heard of distributive law. And why do you mock me? I came here for help, not to be mocked. If there's no answer, fine, there's no answer. I'm here because I drew the same conclusion; there is no answer to what I seek. If the answer was so easy or possible, I likely wouldn't have come here. – Mine Sep 06 '17 at 06:45
  • Okay. $a = bx + y \implies a = x + [(b-1)x + y]$. That's it! You can't just make all the $(b-1)x$ disappear. But depending on the value of $(b-1)$ and $x$ it's possible that $(b-1)x \equiv somethingelse \mod p$. But there is utterly no way to know in general what it would be. – fleablood Sep 06 '17 at 06:46
  • Thank, you, that's all I was looking for. Unfortunately, even in my iteration, there is no applied value to x so, yes, there is no answer. – Mine Sep 06 '17 at 06:47
  • "No, I've never heard of distributive law." WHAT?!?!?!?!?!?!?!?!? $b(x + a) = bx + ba$. That's a very fundamental rule. You cant factor $bx + a = b(x+a)$. You just can't. – fleablood Sep 06 '17 at 06:51
  • It seems you overlooked the possibility that it does hold when $,ab\equiv a\pmod{!n}$ as I explain in my answer. But probably @Mine was hoping it would hold more generally (and made an error in their derivation that led them to believe so). – Bill Dubuque Sep 06 '17 at 14:46
  • @fleablood understanding a concept and knowing of the nomenclature for the concept are two separate things. And you keep ignoring what I'm saying. I didn't say that what I wanted could be done. I drew the same conclusion as you before coming here to post my question; there is no answer as I want it. That's why I came here. Why can't you wrap your mind around that? I need the equation to be as I've stated to apply it to another set of equations. if it isn't $a= x+/-$ then that means there is no solution to my other equation. Which is a valid answer. I just wanted to make sure. – Mine Sep 06 '17 at 17:47