4
$\begingroup$

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.

4 Answers 4

9

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$.

3

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$

1

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.

  • 0
    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.2012-07-04
0

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)$