#9 Hua Luo Geng.

If a = 3 × 1 0 2017 a=3 \times 10^{2017} and b = 2 × 1 0 2017 + 1 b=2\times 10^{2017} +1 , find gcd ( a , b ) \gcd(a,b) .

35 1 3 21

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

Chew-Seong Cheong
Aug 20, 2017

We note that a = 2 2017 × 3 × 5 2017 a = 2^{2017}\times 3 \times 5^{2017} has the prime factors 2, 3 and 5 and that:

b 2 × 1 0 2017 + 1 1 (mod 2) 2 ∤ b \begin{aligned} b & \equiv 2 \times 10^{2017} + 1 \equiv 1 \text{ (mod 2)} \implies \color{#D61F06} 2 \not \mid b \end{aligned}

b 2 × 1 0 2017 mod ϕ ( 3 ) + 1 (mod 3) Since gcd ( 3 , 10 ) = 1 , Euler’s theorem applies. 2 × 1 0 2017 mod 2 + 1 (mod 3) Euler’s totient function ϕ ( 3 ) = 2 2 × 1 0 1 + 1 (mod 3) 21 0 (mod 3) 3 b \begin{aligned} b & \equiv 2 \times 10^{\color{#3D99F6}2017 \text{ mod }\phi (3)} + 1 \text{ (mod 3)} & \small \color{#3D99F6} \text{Since }\gcd(3,10)=1 \text{, Euler's theorem applies.} \\ & \equiv 2 \times 10^{\color{#3D99F6}2017 \text{ mod }2} + 1 \text{ (mod 3)} & \small \color{#3D99F6} \text{Euler's totient function }\phi (3) = 2 \\ & \equiv 2 \times 10^{\color{#3D99F6}1} + 1 \text{ (mod 3)} \\ & \equiv 21 \equiv 0 \text{ (mod 3)} \implies \color{#3D99F6} 3 \mid b \end{aligned}

b 2 × 1 0 2017 + 1 1 (mod 5) 5 ∤ b \begin{aligned} b & \equiv 2 \times 10^{2017} + 1 \equiv 1 \text{ (mod 5)} \implies \color{#D61F06} 5 \not \mid b \end{aligned}

Therefore, 3 is the only common factor of a a and b b and hence gcd ( a , b ) = 3 \gcd(a,b)=3 .

Marco Brezzi
Aug 20, 2017

Using the Euclidean algorithm

gcd ( 3 1 0 2017 , 2 1 0 2017 + 1 ) = gcd ( 3 1 0 2017 ( 2 1 0 2017 + 1 ) , 2 1 0 2017 + 1 ) = gcd ( 1 0 2017 1 , 2 1 0 2017 + 1 ) = gcd ( 1 0 2017 1 , 2 1 0 2017 + 1 2 ( 1 0 2017 1 ) ) = gcd ( 1 0 2017 1 , 3 ) \begin{aligned} \gcd(3\cdot 10^{2017},2\cdot 10^{2017}+1)&=\gcd(3\cdot 10^{2017}-(2\cdot 10^{2017}+1),2\cdot 10^{2017}+1)\\ &=\gcd(10^{2017}-1,2\cdot 10^{2017}+1)\\ &=\gcd(10^{2017}-1,2\cdot 10^{2017}+1-2(10^{2017}-1))\\ &=\gcd(10^{2017}-1,3) \end{aligned}

Which is 1 1 or 3 3 , depending on whether 1 0 2017 1 10^{2017}-1 is divisible by 3 3 or not

1 0 2017 1 ( 3 3 + 1 ) 2017 1 1 2017 1 0 m o d 3 10^{2017}-1\equiv(3\cdot 3+1)^{2017}-1\equiv 1^{2017}-1\equiv 0\mod 3

Hence

gcd ( 3 1 0 2017 , 2 1 0 2017 + 1 ) = 3 \gcd(3\cdot 10^{2017},2\cdot 10^{2017}+1)=\boxed{3}

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...