# number exponentiation

• Oct 25th 2010, 06:30 AM
teps
number exponentiation
"Is there an exponent of number $\displaystyle 3 ( 3^x )$ that ends with 0001 in decimal system?" Hope you understood.
It can be written like this :
$\displaystyle 3^x=10000*k+1$. Find x
• Oct 25th 2010, 12:56 PM
Opalg
Quote:

Originally Posted by teps
"Is there an exponent of number $\displaystyle 3 ( 3^x )$ that ends with 0001 in decimal system?" Hope you understood.
It can be written like this :
$\displaystyle 3^x=10000*k+1$. Find x

Hint: Use Euler's theorem. If you want the actual value of $\displaystyle x$, you will need to compute $\displaystyle \varphi(10000)$. See here for how to do that.
• Oct 25th 2010, 12:56 PM
HappyJoe
This can be done by a pigeon hole argument.

Choose 10001 different integers $\displaystyle \{x_1,x_2,\ldots,x_{10001}\}$. Since there are 10000 remainders upon division by 10000, two of the numbers $\displaystyle x$ and $\displaystyle y$ in our set must have the property that $\displaystyle 3^x$ and $\displaystyle 3^y$ have the same remainder when divided by 10000. Say $\displaystyle x>y$.

Hence $\displaystyle 3^x-3^y = 10000k$ for some integer $\displaystyle k$, whereas $\displaystyle 3^y(3^{x-y}-1) = 10000k$. But 10000 and $\displaystyle 3^y$ are relatively prime, hence $\displaystyle 3^{x-y}-1 = 10000l$ for some integer $\displaystyle l$, like you asked for.
• Oct 26th 2010, 06:08 AM
teps
Thank you. Got it :)