1) Find the last digit of the decimal expansion of $\displaystyle 7^{999,999}$

2) Show that ifais an integer such thatais not divisible by 3 or such thatais divisible by 9, then $\displaystyle a^7$ = a (mod 63)

Printable View

- Oct 7th 2010, 07:46 AMJanu42Euler's Theorem Questions
1) Find the last digit of the decimal expansion of $\displaystyle 7^{999,999}$

2) Show that if*a*is an integer such that*a*is not divisible by 3 or such that*a*is divisible by 9, then $\displaystyle a^7$ = a (mod 63) - Oct 7th 2010, 07:56 AMundefined
- Oct 7th 2010, 08:08 AMJanu42
I don't get what you're doing for #2. I'm confused on the question I think. When it says "such that a is not divisible by 3, or such that a is divisible by 9".... If it was divisible by 9, it's divisible by 3. I don't get what's going on really in this question and how it relates to Euler's.

- Oct 7th 2010, 08:12 AMundefined
"Or" usually means "inclusive or" but in this case "inclusive or" and "exclusive or" lead to the same interpretation since "not divisible by 3" and "divisible by 9" are mutually exclusive. So we have two cases.

It's fairly standard procedure to break down moduli into prime powers; for example we might do this in order to later apply the Chinese Remainder Theorem.

So let $\displaystyle m_1=9,m_2=7$ and prove that in both cases we get the desired result. - Oct 7th 2010, 09:59 AMJanu42
Let me see if I understand this right. I'm doing two separate cases. For each, am I trying to prove that $\displaystyle a^7$ = x (mod 7) and $\displaystyle a^7$ = y (mod 63), where x is either

*a*or 1 and y is the other? Thereby when I use the CRT I multiply*a** 1 to get a making $\displaystyle a^7$ = a (mod 63)? - Oct 7th 2010, 10:26 AMundefined
All we want to show is that $\displaystyle a^7\equiv a\pmod{63}$ and to do so we show that $\displaystyle a^7\equiv a\pmod{9}$ and $\displaystyle a^7\equiv a\pmod{7}$.

Case 1: $\displaystyle a\not\equiv0\pmod{3}$

Then gcd(a,9)=1 and $\displaystyle a^7\equiv a\pmod{9}$ by Euler's theorem since eulerphi(9)=6.

Now either $\displaystyle a\equiv0\pmod{7}$ or $\displaystyle a\not\equiv0\pmod{7}$. In the former case, we have $\displaystyle a^7\equiv0^7\equiv0\equiv a\pmod{7}$. In the latter case we have gcd(a,7)=1 and eulerphi(7)=6 so as before $\displaystyle a^7\equiv a\pmod{7}$.

Therefore in this case $\displaystyle a^7\equiv a\pmod{63}$

Case 2: $\displaystyle a\equiv0\pmod{9}$

Try it. - Oct 7th 2010, 01:50 PMJanu42
- Oct 7th 2010, 01:54 PMundefined
- Oct 7th 2010, 03:05 PMJanu42
- Oct 7th 2010, 03:15 PMundefined
$\displaystyle 7^{999999}\equiv7^{4\cdot249999+3}\equiv7^{4\cdot2 49999}\cdot7^3\equiv(7^4)^{249999}\cdot7^3\equiv1^ {249999}\cdot7^3\equiv7^3\pmod{10}$

But when you see how it works you skip all the intermediate steps

$\displaystyle 7^{999999}\equiv7^{999999\ \text{'mod'}\ \varphi(10)}\pmod{10}$

So now all you need to do is find out what the last digit of $\displaystyle \,7^3$ is.