0
$\begingroup$

A well known demonstration for number-theoretical properties is the following :

A two-digit-number is raised to the $5$ th power and the original number has to be found.

It can be shown with the Carmichael function or with easy modular arithmetic, that the ending digit of the $5$ power is the same as the ending digit of the original number. We have

$$n^5\equiv n\mod 10$$ for every integer $n$

To get the first digit, one method is to cancel the last $5$ digits and to find $k$ , such that $k^5$ is smaller , but $(k+1)^5$ is larger than the resulting number (In the case of the ending digit $0$, the last non-zero digit is the first digit of the original number).

I wonder whether the first digit can be determined faster and without memorizing the $5$-th powers of the numbers $1$ to $9$.

For example, does determining the given number modulo $9$ or modulo $11$ help ?

What is the easiest way to find the first digit ?

$\endgroup$
  • $\begingroup$ The solution has to be determined without electronic help and without writing anything down on a paper. $\endgroup$ – Peter May 6 '17 at 19:13
  • 1
    $\begingroup$ this number can be written in the form $$10a+b$$ and then? $\endgroup$ – Dr. Sonnhard Graubner May 6 '17 at 19:30
  • $\begingroup$ $10 = 2\cdot 5 $, so primitive root modulo 10 exists. 3 is one of them (four in total). If a given $n$ is coprime with 10, maybe you can associate $n$ with some power of 3 then mod 10 to get what you want quicker? $\endgroup$ – swoopin_swallow May 6 '17 at 19:55
  • $\begingroup$ There are a few tools left !!!. $\endgroup$ – Felix Marin May 9 '17 at 2:48
  • $\begingroup$ @FelixMarin True but if we allow, for example the notification of the $5$th powers upto $9^5$, it is trivial to determine the first digit. What I search is some easy rule (for example involving the digit sum or the number of digits) allowing to determine the first digit quickly and with a "in the head"-calculation. $\endgroup$ – Peter May 10 '17 at 10:07
1
$\begingroup$

Reduction modulo $11$ doesn't help much, unless the result turns out to be $0$ (then you immediately have the first digit: it's the same as the second), since $a^5 \equiv \pm 1 \pmod{11}$ if $11\nmid a$. A remainder of $+1$ or $-1$ would tell you whether $n$ is a quadratic residue modulo $11$, but that only reduces the options by half.

Reducing modulo $9$ is better. Since $\varphi(9) = 6$, we have $n^5 \equiv n^{-1} \pmod{9}$ if $3\nmid n$, so if $n$ wasn't divisible by $3$, that immediately tells you the remainder of $n$ modulo $9$, and thus - unless $0$ is a valid first digit - determines $n$. If $n$ was divisible by $3$, that leaves you with three options, but those three options should be fairly easy to distinguish.

But you can also reduce modulo $7$ - again, $n^5 \equiv n^{-1} \pmod{7}$ if $7 \nmid n$. That gives you the remainder of $n$ modulo $7$. And if the reduction modulo $9$ shows $3\mid n$, together with the remainder modulo $7$, the number is determined.

$\endgroup$

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.