Find the appropriate product

Question

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.

Answer 1

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$.