number exponentiation

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

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

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

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

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