I'm missing 6

What is the remainder when 4 5 23 45^{23} is divided by 7?


The answer is 5.

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.

5 solutions

Rick B
May 13, 2015

4 5 23 3 23 = ( 3 3 ) 7 3 2 ( 1 ) 7 2 = 2 5 ( m o d 7 ) 45^{23} \equiv 3^{23} = (3^3)^7 \cdot 3^2 \equiv (-1)^7 \cdot 2 = -2 \equiv \boxed{5} \pmod{7}

Moderator note:

Good eye for spotting 3 3 1 ( m o d 7 ) 3^3 \equiv -1 \pmod 7 .

Sarthak Rath
May 13, 2015

45 3 ( m o d 7 ) 45 \equiv 3 \pmod{7}

4 5 2 2 ( m o d 7 ) 45^2 \equiv 2 \pmod{7}

4 5 4 4 ( m o d 7 ) 45^4 \equiv 4 \pmod{7}

4 5 5 5 ( m o d 7 ) 45^5 \equiv 5 \pmod{7} from 1 and 3

4 5 6 1 ( m o d 7 ) 45^6 \equiv 1 \pmod{7} from 1 and 4

4 5 18 1 ( m o d 7 ) 45^{18} \equiv 1 \pmod{7}

4 5 23 5 ( m o d 7 ) 45^{23} \equiv 5 \pmod{7} from 4 and 6

hence the answer is 5 \boxed{5}

Moderator note:

This works too!

Systematic approach:

  1. By Fermat, 4 5 23 3 23 3 23 m o d 6 3 1 ( m o d 7 ) 45^{23}\equiv 3^{23}\equiv 3^{23~\bmod~6}\equiv 3^{-1}\pmod7

  2. We use Extended Euclidean Algorithm to find the modular inverse of 3 3 modulo 7 7 (it exists since gcd ( 3 , 7 ) = 1 \gcd(3,7)=1 ). So,

z 3 1 ( m o d 7 ) 3 z 1 ( m o d 7 ) z 5 ( m o d 7 ) z\equiv 3^{-1}\pmod7\implies 3z\equiv 1\pmod7\implies z\equiv \color{#3D99F6}{5}\pmod7

We used the following result from the Extended Euclidean Algorithm to get our answer:

gcd ( 3 , 7 ) = 1 = 5 × 3 + ( 2 ) × 7 \gcd(3,7)=1=\color{#3D99F6}{5}\times 3 + \color{#D61F06}{(-2)}\times 7

Prasun Biswas - 6 years, 1 month ago

Log in to reply

It's not necessarily to invoke Extended Euclidean Algorithm (all the time!). You could just have 3 23 m o d 6 3 5 ( 3 2 ) 2 3 2 2 3 5 \ldots \equiv 3^{23 \bmod \ 6} \equiv 3^5 \equiv (3^2)^2 \cdot 3 \equiv 2^2 \cdot 3 \equiv 5 . Unless you know that 1 = 5 × 3 2 × 7 1 = 5\times 3 - 2 \times 7 at the back of your head, it's not much easier. Your "systematic approach" is much difficult compared to the purely Fermat's Little Theorem approach.

Pi Han Goh - 6 years, 1 month ago

Log in to reply

Well, everyone has their own preferences.

Prasun Biswas - 6 years, 1 month ago

Log in to reply

@Prasun Biswas It's just 3 1 1 3 6 3 2 5 ( m o d 7 ) 3^{-1}\equiv \frac{1}{3}\equiv \frac{-6}{3}\equiv -2\equiv 5\pmod{7} or to make it more clear we have 3x\equiv 1\equiv -6\stackrel{:3}\iff x\equiv -2\equiv 5 mod 7 7 , which is just another way of writing it. I really much prefer this to Extended Euclidean Algorithm.

mathh mathh - 6 years, 1 month ago

i dont know the concept of mod can you explain it a little bit..

Harshi Singh - 6 years, 1 month ago

Log in to reply

https://brilliant.org/math/number-theory/modular-arithmetic/

Sarthak Rath - 6 years, 1 month ago
Mathh Mathh
May 14, 2015

3 4 5 23 3 3 23 Fermat 3 24 ( m o d 6 ) 3 0 3\cdot 45^{23}\equiv 3\cdot 3^{23}\stackrel{\text{Fermat}}\equiv 3^{24\!\pmod{\!6}}\equiv 3^0

\equiv 1\equiv -6\stackrel{:3}\iff 45^{23}\equiv -2\equiv 5 mod 7 7 .

Or written in another way

4 5 23 3 23 3 23 ( m o d 6 ) 3 1 45^{23}\equiv 3^{23}\equiv 3^{23\!\pmod{\!6}}\equiv 3^{-1}

1 3 6 3 2 5 \equiv \frac{1}{3}\equiv \frac{-6}{3}\equiv -2\equiv 5 mod 7 7 .

Chew-Seong Cheong
May 13, 2015

4 5 23 ( 42 + 3 ) 23 ( m o d 7 ) 3 23 ( m o d 7 ) 9 11 ˙ 3 ( m o d 7 ) 3 ˙ 2 11 ( m o d 7 ) 3 ˙ 2 2 ˙ 8 3 ( m o d 7 ) 3 ˙ 2 2 ˙ 1 ( m o d 7 ) 12 ( m o d 7 ) 5 ( m o d 7 ) \begin{aligned} 45^{23} & \equiv (42+3)^{23} \pmod{7} \equiv 3^{23} \pmod{7} \equiv 9^{11}\dot{}3 \pmod{7} \\ & \equiv 3\dot{}2^{11} \pmod{7} \equiv 3\dot{}2^2\dot{}8^3 \pmod{7} \equiv 3\dot{}2^2\dot{}1 \pmod{7} \\ & \equiv 12 \pmod{7} \equiv \boxed{5} \pmod{7} \end{aligned}

Moderator note:

You could simplify you solution by a bit. Hint: Fermat.

Oscar Rojas
May 13, 2015

45^6=1 (mod 7),¨fermat. 45 = 3 (mod 7) ,
( 45^ 6 ) 3 * 45 ^ 5 = a mod 7. (1 ) ^ 3 * (3) ^ 5 = a mod 7..... 243 = 5 mod 7 a = 5 the remainder

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...