the-rest-of-the-division-euclidienne-of-10-99-by-13-17-is-

Question Number 165099 by SANOGO last updated on 26/Jan/22

t h e r e s t o f t h e d i v i s i o n e u c l i d i e n n e o f

10^{99} b y 13 \times 17 i s ?

Commented by Rasheed.Sindhi last updated on 26/Jan/22

T r a n s l a t e i n t o E n g l i s h a l s o .

Answered by mr W last updated on 27/Jan/22

13 \times 17 = 221

10^{99} = {(1000)}^{33}

= {(4 \times 221 + 116)}^{33}

⊨ 116^{33}

= 116 \times {(60 \times 221 + 196)}^{16}

⊨ 116 \times 196^{16}

= 116 \times {(173 \times 221 + 183)}^{8}

⊨ 116 \times 183^{8}

= 116 \times {(151 \times 221 + 118)}^{4}

⊨ 116 \times 118^{4}

= 116 \times {(60 \times 221 + 664)}^{2}

⊨ 116 \times 664^{2}

= 116 \times (1995 \times 221 + 1)

⊨ 116 = a n s w e r

w i t h ⊨ i m e a n

“ h a s t h e s a m e r e m a i n d e r {a s}^{″}

Answered by Rasheed.Sindhi last updated on 27/Jan/22

Another way \dots

S a y, 10^{99} \equiv x (m o d 221) [∵ 13 \times 17 = 221]

∵ \gcd (10, 221) = 1

∴ 10^{ϕ (221)} \equiv 1 (m o d 221)

N o w, ϕ (221) = 221 (1 - \frac{1}{13}) (1 - \frac{1}{17}) = 192

∴ 10^{192} \equiv 1 (m o d 221)

T r y i n g f o r d i c f e r e n t d i v i s o r s o f 192

W e c a n s e e t h a t

10^{48} \equiv 1 (m o d 221)

{(10^{48})}^{2} \equiv {(1)}^{2} (m o d 221)

10^{96} \equiv 1 (m o d 221) \dots \dots \dots (i)

A l s o c a n b e o b s e r v e d t h a t

10^{3} \equiv 116 (m o d 221) \dots \dots (i i)

(i) \times (i i) : 10^{99} \equiv 116 (m o d 221)

x = 116