2

I have a use for a function that represents the least amount that must be added to an integer $x$ to make it a multiple of $y$.

I.e., if we call that function $\Delta$, then $\Delta(\frac{x}{y}) = y\lceil\frac{x}{y}\rceil-x$

If there isn't an accepted notation, should I use the Delta symbol or an abbreviation, such as "def" for "deficit" or "dif" for "difference"? And is it clearer to express it in the form $\Delta(\frac{x}{y})$ or $\Delta(x,y)$?

For my purpose $x$ and $y$ will always be mutually prime, and positive.

Joe Slater
  • 440
  • 2
  • 10
  • It is definitely wrong to write it as $\Delta(\frac xy)$, since it depends on the integers $x$ and $y$ separately, not just on the rational number $\frac xy$. – Marc van Leeuwen Jun 30 '19 at 13:34
  • So, you have three quantities: the smaller integer, the larger integer, and the "bump" to the larger integer that makes it a multiple of the smaller integer. To help the reader, I would recommend we refer to these quantities as $n$, $N$, and $b_n(N)$. [With this notation, $0 \leq b_n(N) < n \leq N$ .] – Selrach Dunbar Jun 30 '19 at 13:39
  • @SelrachDunbar The bump may be greater than or equal to the smaller integer, e.g. $x=2$, $y = 5$, $\Delta = 3$. – peterwhy Jun 30 '19 at 14:02
  • @peterwhy I see. I intended the notation to denote that $0 < n \leq N$. In this case the bump we need to give the larger integer (i.e. "the bump of the larger integer") is as above. If we want to consider the bump we need to give the smaler integer it would be, as you pointed out $b_N(n) = N-n$. Thanks! – Selrach Dunbar Jun 30 '19 at 14:49
  • @peterwhy In fact, your answer shows that, if $0<n \leq N$ then $b_n(N)= n - (N \bmod n)$. – Selrach Dunbar Jun 30 '19 at 15:01
  • @SelrachDunbar Yes, that was in revision 1, which I did not like, because a special case is when $N\bmod n = 0$ then $b_n(N) = 0$. – peterwhy Jun 30 '19 at 15:06
  • @peterwhy Yes. The condition in my last comment needs to be $0<n<N$ for that formula to work. I like your updated answer which gives a single expression for $b_n(N)=(-N) \bmod n$ which works for any $0<n, , N \in \mathbb{N}$ (regardless of which is bigger). – Selrach Dunbar Jun 30 '19 at 16:14
  • Must the increment $\delta$ be nonnegative, e.g. for $,x,y = 6,5,$ is $,\delta = 4\ $ or $,-1$ (least magnitude). Either way it has obvious expression in terms of $\bmod = $ remainder. – Bill Dubuque Jun 30 '19 at 16:50
  • @SelrachDunbar $0<n<N$ is not sufficient, as $N$ could be a multiple of $n$ and then $N\bmod n = 0$. – peterwhy Jun 30 '19 at 18:17
  • @Bill Dubuque: yes, I need it to be the least positive number such that adding it to x makes x a multiple of y. – Joe Slater Jul 01 '19 at 00:58
  • @JoeSlater So $,\delta$ can't be $0,,$ i.e. if $, x,$ is a multiple of $,y,$ then you add $,\delta =y,$ instead of $,\delta = 0?\ \ $ – Bill Dubuque Jul 01 '19 at 01:06
  • No, sorry, I should have said "least non-negative" number I suppose. I.e., 0 >= δ < x – Joe Slater Jul 01 '19 at 04:54

2 Answers2

2

When performing division with remainder:

$$n = dq+r$$

where $0\le r <d$ and $r$ is sometimes denoted $n \bmod d$, so

$$n = d\left\lfloor\frac nd\right\rfloor + (n\bmod d)$$

Consider dividing $-x$ by $y$ with remainder,

$$\begin{align*} -x &= y\left\lfloor \frac{-x}{y}\right\rfloor + (-x \bmod y)\\ &= -y\left\lceil\frac xy\right\rceil + (-x\bmod y)\\ y\left\lceil\frac xy\right\rceil - x &= (-x) \bmod y\\ \Delta &= (-x) \bmod y \end{align*}$$

An alternative view, $\Delta$ is a number that satisfy both $0\le \Delta < y$ and

$$\begin{align*} x + \Delta &= ky\\ x + \Delta &\equiv 0 \pmod y\\ \Delta &\equiv -x \pmod y \end{align*}$$

Then $\Delta$ is just $(-x)\bmod y$.

peterwhy
  • 22,256
-1

@JoeSlater In terms of your original question. After the above discussion in the comments, I would recommend, as a notation $b_y(x)$ to represent the "bump of $x$ you need to make it a multiple of $y$." As @peterwhy has shown in his answer above, this quantity is given by the expression:

$$b_y(x)=(-x) \bmod y$$

for all positive integers $x$ and $y$.

(So, if you don't mind writing a little more, you could just write this expression every time you need to refer to this quantity.)

Selrach Dunbar
  • 749
  • From what I understand, expressing numbers as "x mod y" reflects older programming languages' implementation of the "modulo" function, not the mathematical definition. What "x mod y" returns is actually a class of numbers: ... x-2y, x-y, x, x+y, x+2y ..., so "-x mod y" wouldn't work as a definition without stipulating that it was confined to the least positive value. – Joe Slater Jul 01 '19 at 01:00
  • @JoeSlater Yes. In mathematics, as you have stated, "x mod y" represents a class of numbers. (Actually, this operation breaks the integers up into y "equivalence classes".) I suspect a computer, is going to be very efficient and store the output euqivalence class as exactly the representative of that equivalence class you want, i.e. the least positive value (or 0) that is in that equivalence calss. – Selrach Dunbar Jul 01 '19 at 20:34