Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This question came in a competitive exam I took recently.

The last digit of LCM of $3^{2003} - 1$ and $3^{2003} + 1$ is

is there any strategy by which we can quickly determine the answer? I am hoping there is, since the question came in a timed competitive test.

share|improve this question

4 Answers 4

up vote 8 down vote accepted

The GCD of $x$ and $y$ divides $x-y$, hence the GCD $3^{2003}-1$ and $3^{2003}+1$ is either $1$ or $2$; it is easy to check that both numbers are even, so this GCD of these is 2.

The LCM of $x$ and $y$ multiplied by the GCD of $x$ and $y$ equals $x \times y$. So the LCM in question equals $\frac{(3^{2003}-1) \times (3^{2003}+1)}{2} = \frac{3^{4006}-1}{2}$.

$3^n \mod 20$ gives us the following sequence: $1, 3, 9, 7, 1, 3, 9, 7, \cdots$; hence $3^{4006} \mod 20 = 3^2 \mod 20 = 9$, and the answer is $\frac{9-1}{2} = 4$.

share|improve this answer

Hint $\ $ Their gcd is $2$ since for odd $\rm\:k,\ (k\!+\!1,k\!-\!1) = (k\!+\!1,2)=2.\:$ So their lcm = product$/2$. Determining the product$/2$ mod $10$ requires determing the product mod $20.\,$ But mod $20$ we have $\rm(3^n\!-\!1)(3^n\!+\!1) = 9^n\!-\!1 = 0,8,0,8\ldots$ by $\,9^2\! = 81\equiv 1.\,$ Thus $\rm\,9^{2003}\!-1 = \color{#C00}{8+20\,k},\,$ hence

$$\rm \frac{(3^{2003}\!-1)(3^{2003}\!+1)}2\, =\, \frac{9^{2003}\!-1}2\, =\ \color{#C00}{4+10\,k}\ \ \ has\ last\ digit = 4$$

share|improve this answer

By euclid's algorithm(http://en.wikipedia.org/wiki/Euclidean_algorithm), $\gcd (a,b)=\gcd (a,a-b)$. Here, $\gcd(3^{2003}+1,3^{2003}-1)=\gcd(3^{2003}+1,2)=2$ (since $3^{2003}+1$ is an even integer).LCM=$ab/\gcd= \frac{3^{4006}-1}{2}.$ Now $ 3^4=1\pmod{20} \implies (3^4)^{1001}.9=-11\pmod {20}\implies {3^{4006}-1}=-12\pmod{20}=8\pmod{20} \implies $ $\frac{3^{4006}-1}{2}=8/2=4$ is the last digit.

share|improve this answer
    
The OP wants LCM not GCD. –  lhf Jul 3 '12 at 11:24
1  
You need to determine the product mod 20, to determine the product/2 mod 10. –  Bill Dubuque Jul 3 '12 at 17:09
    
As an example of what Bill Dubuque said, observe that (9-1)/2 = 4 but (19-1)/2 = 9. So to find the last digit of (x-1)/2, it is not enough to know the last digit of x. –  ShreevatsaR Jul 4 '12 at 4:18

gcd($3^{2003}+1\ , 3^{2003}-1$) $$=gcd(3^{2003}+1\ , 2)\ as\ gcd(a,b)=gcd(a,a-b)\ and\ 3^{2003}+1\ -(3^{2003}-1)=2$$ =2 as $3^n-1$ is even for any natural number n.

So,lcm($3^{2003}+1\ , 3^{2003}-1$)= ($3^{2003}+1)(3^{2003}-1$)/gcd($3^{2003}+1,\ 3^{2003}-1$)=($3^{4006}-1)/2$

Now, using Euler's Totient Theorem, $a^\phi(m)≡1(mod\ m)$ where (a,m)=1

So, $a^{k\phi(m)+h}≡a^h(mod\ m)$

Here (3,10)=(3,100)=1

Now, $\phi(10)=phi(2)phi(5)=1*4=4\ and\ \phi(100)=10phi(10)=40$

4006≡6(mod 40)≡2(mod 4)

$3^{4006}≡3^6(mod\ 100)≡3^2(mod\ 10)$

So, $lcm(3^{2003}+1\ , 3^{2003}-1)≡(3^6-1)/2(mod\ 100)≡(3^2-1)/2(mod\ 10)≡14(mod\ 100)≡4(mod\ 10)$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.