Remember Fermat?

If x = 2 20 + 3 30 + 4 40 + 5 50 + 6 60 x={ 2 }^{ 20 }+{ 3 }^{ 30 }+{ 4 }^{ 40 }+{ 5 }^{ 50 }+{ 6 }^{ 60 } , find x mod 7 x \text{ mod } 7 .


The answer is 0.

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

Applying Fermat's little theorem : 2 6 1 mod 7 2 20 = ( 2 6 ) 3 2 2 4 mod 7 2^6 \equiv 1 \text{ mod 7} \Rightarrow 2^{20} = (2^6)^{3}\cdot 2^2 \equiv 4 \text{ mod 7} 3 6 1 mod 7 3 30 = ( 3 6 ) 5 1 mod 7 3^6 \equiv 1 \text{ mod 7} \Rightarrow 3^{30} = (3^6)^{5} \equiv 1 \text{ mod 7} 4 6 1 mod 7 4 40 = ( 4 6 ) 6 4 4 4 mod 7 4^6 \equiv 1 \text{ mod 7} \Rightarrow 4^{40} = (4^6)^{6}\cdot 4^4 \equiv 4 \text{ mod 7} 5 6 1 mod 7 5 50 = ( 5 6 ) 8 5 2 4 mod 7 5^6 \equiv 1 \text{ mod 7} \Rightarrow 5^{50} = (5^6)^{8} \cdot 5^2 \equiv 4 \text{ mod 7} 6 6 1 mod 7 6 60 = ( 6 6 ) 10 1 mod 7 . 6^6 \equiv 1 \text {mod 7} \Rightarrow 6^{60} = (6^6)^{10} \equiv 1 \text{ mod 7}. Therefore, 2 20 + 3 30 + 4 40 + 5 50 + 6 60 4 + 1 + 4 + 4 + 1 = 14 0 mod 7 2^{20} + 3^{30} + 4^{40} + 5^{50} +6^{60} \equiv 4 +1 + 4 + 4 + 1 = 14 \equiv 0 \text{ mod 7}

Since 2, 3, 4, 5, and 6 are coprime to 7, we can apply Euler's theorem . We note that Euler's totient function ϕ ( 7 ) = 6 \phi(7) = 6 . Then, we have:

x ( 2 20 + 3 30 + 4 40 + 5 50 + 6 60 ) (mod 7) ( 2 3 × 6 + 2 + 3 5 × 6 + 4 6 × 6 + 4 + 5 8 × 6 + 2 + 6 10 × 6 ) (mod 7) ( ( 2 ϕ ( 7 ) ) 3 2 2 + ( 3 ϕ ( 7 ) ) 5 + ( 4 ϕ ( 7 ) ) 6 4 4 + ( 5 ϕ ( 7 ) ) 8 5 2 + ( 6 ϕ ( 7 ) ) 10 ) (mod 7) ( 1 2 2 + 1 + 1 4 4 + 1 5 2 + 1 ) (mod 7) ( 2 2 + 1 + 4 4 + 5 2 + 1 ) (mod 7) ( 4 + 1 + 2 6 + 2 + 25 + 1 ) (mod 7) ( 4 + 1 + 4 + 4 + 1 ) (mod 7) 14 (mod 7) 0 (mod 7) \begin{aligned} x & \equiv \left(2^{20} + 3^{30} + 4^{40} + 5^{50} + 6^{60} \right) \text{(mod 7)} \\ & \equiv \left(2^{\color{#D61F06}{3\times 6}+2} + 3^{\color{#D61F06}{5\times 6}} + 4^{\color{#D61F06}{6\times 6}+4} + 5^{\color{#D61F06}{8\times 6}+2} + 6^{\color{#D61F06}{10\times 6}} \right) \text{(mod 7)} \\ & \equiv \left(\color{#D61F06}{\left(2^{\phi(7)} \right)^3}2^2 + \color{#D61F06}{\left(3^{\phi(7)} \right)^5} + \color{#D61F06}{\left(4^{\phi(7)} \right)^6}4^4 + \color{#D61F06}{\left(5^{\phi(7)} \right)^8}5^2 + \color{#D61F06}{\left(6^{\phi(7)} \right)^{10}} \right) \text{(mod 7)} \\ & \equiv \left(\color{#D61F06}{1}\cdot 2^2 + \color{#D61F06}{1} + \color{#D61F06}{1}\cdot 4^4 + \color{#D61F06}{1}\cdot 5^2 + \color{#D61F06}{1} \right) \text{(mod 7)} \\ & \equiv \left(2^2 + 1 + 4^4 + 5^2 + 1 \right) \text{(mod 7)} \\ & \equiv \left(4 + 1 + 2^{6+2} + 25 + 1 \right) \text{(mod 7)} \\ & \equiv \left(4 + 1 + 4 + 4 + 1 \right) \text{(mod 7)} \\ & \equiv 14 \text{(mod 7)} \\ & \equiv \boxed{0} \text{(mod 7)} \end{aligned}

Sir i have separately calculated the remainder and then added like @Guillermo Templado has done .I can't understand what have you done , please can you explain it to me ?? Thank you

Chirayu Bhardwaj - 4 years, 9 months ago

Log in to reply

He has done essentially what I done. Euler's theorem is essentially Fermat's little theorem when the module(in this case 7) is a prime number. He's just also applied elemental propierties of congruences like me, and Euler's theorem... Check also Euler's totient function please and I think in 10 minutes you'll understand it. I don't either want to be upset, sorry.

Guillermo Templado - 4 years, 9 months ago

Log in to reply

I am sorry if someone was upset. I just wanted to show that the solution can be presented in one go.

Chew-Seong Cheong - 4 years, 9 months ago

Thank you . I will see it :).

Chirayu Bhardwaj - 4 years, 9 months ago

I have added a line to explain it. For example 2 20 2 3 × 6 + 2 ( 2 ϕ ( 7 ) ) 3 2 2 1 3 2 2 2^{20} \equiv 2^{3 \times 6 + 2} \equiv (2^{\phi(7)})^32^2 \equiv 1^32^2 \equiv 2 2 2^2 \equiv 4 (mod 7) 4 \text{ (mod 7)} .

Chew-Seong Cheong - 4 years, 9 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...