1
$\begingroup$

I have a number $n$ and an integer $x$ which ends on $1, 3, 7 \ or\ 9$, meaning that the last digit (rightmost digit) of $x$ is one of those 4 numbers.

Now if $z = x * y$, what number do I have to choose for $y$ such that the $n$ last (rightmost) digits of $z$ are equal to $1$ (I mean the numerical value of the rightmost $n$ digits of $z$ has to be $1$) while ignoring leading zeros.

Examples:

// computes y
long computeY(int n, long x) {
    // ...magic...
    return y;
}
  • computeY(1, 9) == 9 (because 9*9 = 81, take the n rightmost digits, result is 1)

  • computeY(1, 7) == 3 (because 7*3 = 21, take the n rightmost digits, result is 1)

  • computeY(2, 11) == 91 (because 11*91 = 1001, take the n rightmost digits, result is 1, ignore leading zeros)

  • computeY(3, 17) == 353 (because 353*17 = 6001, take the n rightmost digits, result is 1, ignore leading zeros)

  • computeY(5, 11327) == 23263 (because 11327*23263 = 263500001, take the n rightmost digits, result is 1, ignore leading zeros)

I encountered this problem during a programming contest at my school and am stuck, It looks like I have to use number theory but I just don't know where to start.

$\endgroup$
2
$\begingroup$

Suppose that you are given the last $n$ digits of $x$, which is the same as knowing $x \bmod 10^n$. You want to find the last $n$ digits of $y$, that is, $y \bmod 10^n$, given that $xy \bmod 10^n = 1$. Since $xy \equiv 1 \pmod{10^n}$, the solution is $y \bmod 10^n = (x \bmod 10^n)^{-1}$, the inverse being taken in $\mathbb{Z}_{10^n}$. The condition $x \bmod 10 \in \{1,3,5,7\}$ guarantees that $(x,10^n) = 1$, and so the inverse always exists.

In order to calculate the inverse, use the extended GCD algorithm to find $a,b$ such that $a(x \bmod 10^n) + b10^n = 1$, and take $y \bmod 10^n = a \bmod 10^n$.

For example, suppose you know that $x \bmod 10^5 = 11327$. The extended GCD algorithm gives $$ 23263 \cdot 11327 - 2635 \cdot 10^5 = 1, $$ and so $y \bmod{10^5} = 23263$.

$\endgroup$
  • $\begingroup$ Why does $xy \equiv 1 \pmod{10^n} \iff y \bmod 10^n = (x \bmod 10^n)^{-1}$ ? $\endgroup$ – Anna Vopureta Jul 23 '17 at 9:55
  • $\begingroup$ This is the definition of inverse. $\endgroup$ – Yuval Filmus Jul 23 '17 at 17:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.