0

In the following circumstance, is there a way to compute b with certainty, (or assign b a value that would yield the same product modulo k as the actual b would have when multiplied by any other value smaller than k)?

a * b = c mod k

a, b < k

a, c and k are known

(c is a number that already has the modulus applied; in other words a*b could have yielded
 a product either greater or smaller than k, and by how much we don't know.)
גלעד ברקן
  • 550
  • You are asking about modular division here, or more generally modular inverses. Read here about the extended euclidean algorithm to find modular inverses: https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Computing_multiplicative_inverses_in_modular_structures – Noam Nov 23 '16 at 14:17
  • @Noam thanks for the reference. – גלעד ברקן Nov 23 '16 at 14:47

1 Answers1

0

$ab\equiv c\pmod{k}\implies$

$ab-c\equiv0\pmod{k}\implies$

$\exists{n\in\mathbb{N}}:ab-c=nk\implies$

$\exists{n\in\mathbb{N}}:b=(nk+c)/a$

You know $a$, $c$ and $k$, so search for $n\in\mathbb{N}$ such that $(nk-c)/a\in\mathbb{N}$, and assign this value to $b$.

barak manos
  • 43,109
  • Thank you for your answer. Would any n that satisfies the condition yield the same product modulo k as the actual b would have when multiplied by any other value smaller than k? – גלעד ברקן Nov 23 '16 at 14:46
  • You say that $b$ is multiplied by $a$. Why should this work for every other value??? – barak manos Nov 23 '16 at 14:48
  • Oh, what I mean is if I multiplied n by any d mod k would that equal b*d mod k? – גלעד ברקן Nov 23 '16 at 15:01
  • Sorry, but i don't understand the question, nor its relation to my answer. Why would you go around multiplying $n$? It's $n$ that you need to find, then you can conclude the value of $b$. – barak manos Nov 23 '16 at 15:08
  • BTW, please note that I had a sign mistake in the last line (with "$-c$" instead of "$+c$"). – barak manos Nov 23 '16 at 15:13
  • Oops, meant the expression not n itself, sorry. – גלעד ברקן Nov 23 '16 at 15:32
  • You have $a$, $c$ and $k$ at hand. What expression exactly are you referring to? – barak manos Nov 23 '16 at 15:41
  • Lol, thank you for your patience! I'm asking about the discovered b, the expression (nk + c) / a Is there only one answer for the discovered b mod k? – גלעד ברקן Nov 23 '16 at 16:19
  • You can try a couple of numeric examples and find out. I'm pretty sure that there isn't necessarily a single answer. Perhaps there is a single answer if $k$ is prime (or even coprime to $a$), but I'm really sure about this to be honest. – barak manos Nov 23 '16 at 17:10
  • @גלעדברקן: Somebody has down-voted this answer, so it is possibly wrong (they didn't leave any comment, so I cannot tell for sure). – barak manos Nov 23 '16 at 17:51
  • Oh then I'll remove the check mark to hopefully generate more interest. (idk, your logic made sense to me.) – גלעד ברקן Nov 23 '16 at 18:48