Question

show that \(\large \frac{10^{12n-6}-1}{99} \) is not divisible by \(101\) for all \(n \in \mathbb{Z^{+}}\)

Answer 1

In other words show that below equation is not solvable in integers
\[\large 10^{12n-6}-1 = 99\cdot 101k\]

Answer 2

is their a property like
\(\dfrac{a}{b} (mod~c)=\dfrac{a (mod~c)}{b (mod~c)} \)

Answer 3

thats a good start! lets consider an example
\[\dfrac{6}{3} (mod~3) \stackrel{?}{=}\dfrac{6 (mod~3)}{2 (mod~3)} \]

Answer 4

thats invalid

Answer 5

\[2(mod~3) \stackrel{?}{=}\dfrac{0}{2 (mod~3)} \]

Answer 6

so such a rule is not valid

Answer 7

however this is true :
\[a\pmod n \times b\pmod n = ab \pmod n\]

Answer 8

another example to see the mods are not friendly with division :

\[\dfrac{6}{4} (mod~3) \stackrel{?}{=}\dfrac{6 (mod~3)}{4 (mod~3)}\]

Answer 9

\(10^{12n-6}-1\)
is indded divisible by 99,
any way to show \((10^{12n-6}-1)/99\) it in terms of 'n' without any denominator...

bdw, whats the general way to show an integer is not divisible by another integer...? contradiction , or something else in mod arithmetic or what u posted in 1st reply?

Answer 10

tp prove
\(10^{12n-6}-1 ~ mod ~9999 \ne 0 \)

Answer 11

yes \(\dfrac{10^{12n-6}-1}{99}\) gives a nice pattern of numbers :

10101
101010101010101

etc..

Answer 12

10^2=1 mod 99
10^12n-6=1 mod 99
10^(12n-6) -1=0 md 99
this how u show its integer

Answer 13

\([10^{6n-3}-1~ mod ~9999] \times [10^{6n-3}+1~ mod ~9999] \ne 0 \)

Answer 14

we want to show \(10^{12n-6}-1 \not \equiv 0 \pmod {99 \cdot 101}\)

Answer 15

that looks interesting, you factored xD

Answer 16

just to use
\(a\pmod n \times b\pmod n = ab \pmod n
\)
:P

Answer 17

i have some idea for it :P will come back after lunch ...

Answer 18

\(10^{(6n-3)}-1 |9 \\ \implies 10^{(6n-3)}-1 ~mod~ 1111\)
should be shown non-0

Answer 19

that works i think
but we also need to show that \(10^{6n-3}+1 \pmod{1111}\) is not 0

Answer 20

i wasn't sure that ...+1 lso divides 9 or not

Answer 21

Oh I see yeah we still need to show \(10^{6n-3}+1 \pmod{9999}\) is not 0

Answer 22

YES,
does that
...+1 divide 11 ?

Answer 23

\(\begin{align*}
10^{12n-6} -1
&=(10^{6n-3} -1) (10^{6n-1} +1) \\
&=(10^{3(2n-1)} -1) (10^{3(2n-1)} +1) \\
&= ((-10)-1 )(-10 +1)\mod 101\\
&= -11*-9= -2 \mod 101
\end{align*} \)

Answer 24

what about the 99 lol

Answer 25

hehe was just spreading ideas :D

Answer 26

since it does not devide 101
then it does not devide k101 for any k let k be 99
so :P

Answer 27

how is
\(\Large 10^{3(2n-1)}~mod ~101 = -10\)
?

Answer 28

that looks perfect ! @Marki

Answer 29

since it does not devide 101
then it does not devide k101 for any k let k be 99 \(\blacksquare\)

Answer 30

thats it! thats the end of proof xD

Answer 31

is the answer \(\Large \equiv 1 (mod ~~101) \)

Answer 32

over integers+

Answer 33

10^3=(-10) mod 101
=10* (-1) mod 101
2n-1 is odd
so (-1)^3(2n-1 ) = -1 mod 101

now we need to show

10^3=10 ^3k mod b let k be 2n-1
thus
we have
10^3(2n-1)=(-10) mod 101

Answer 34

idk if i made some typos
but @mathmath333 i showed it for 101 only not for both

Answer 35

for both i need Diophantine to find mod and since @ganeshie8 asked only for showing its not divisible without finding exact mod then there is no need

Answer 36

i havn't read ur comments , i just post my idea :
@ganeshie8 , @Marki it's just like the idea for 17 :
Let suppose that it's divisible by 101,then it can be written \( a=101t \).
\( a \equiv 1 ~ (mod ~ 10) \) so \( t \equiv 1 ~ (mod ~ 10) \) too (it can be proven).then \(t=10k+1 \)
therefore \(a=1010k + 101 \).

Answer 37

what if k=5
then a=101000101 ( which is not our sequence )

Answer 38

@PFEH.1999
we can conclude below from Marki's first reply :
\[10^{12n-6}-1 \equiv -2 \pmod {101}\]

Answer 39

since \(10^{12n-6}-1\) is not divisible by \(101\) itself,
it cannot be divisible by \( 99\cdot 101\) also

end of story!

Answer 40

so it doesn't matter what the denominator is :P
unless it makes the fraction as integer

Answer 41

@ganeshie8 i said i havn't been following ur ideas XD

Answer 42

Exactly!
if a number is not divisible by "2", then we can say that it is also not divisible by any multiple of 2

Answer 43

so it doesn't matter what the denominator is :P
unless it makes the fraction as integer


hmm @hartnn at least i showed it gives integer :P

Answer 44

continuing marki's solution
\(\large \tt \begin{align} \color{black}{\dfrac{1}{99}\dfrac{-2}{101}\\~\\
=\dfrac{1}{99}\times \dfrac{-2}{101}\\~\\
=\dfrac{1}{99} \times \dfrac{-101+99}{101}\\~\\
=\dfrac{1}{99}(99)\\~\\
\Large \equiv 1
}\end{align}\)

Answer 45

i am yet to digest why
\(\Large 10^{3(2n-1)}~mod ~101 = -10\)

Answer 46

Ahh that works @PFEH.1999 i was stuck with analyzin g Marki's solution

Answer 47

ok i'll show it again with complicating it

Answer 48

@ganeshie8 is my soln valid

Answer 49

one sec, im going thru..

Answer 50

first let me answer @hartnn 's question on why \(10^{3(2n-1)}~\mod ~101 = -10\)

Answer 51

\[10^{3(2n-1)} \equiv 1000^{2n-1} \equiv (101\times 10 - 10)^{2n-1}\equiv (-10)^{2n-1} \pmod{101}\]

Answer 52

\(\large \begin{align*}
10^{12n-6}-1
&= (10^2)^{6n-3}-1\\
&= (-1)^{3(2n-1)}-1 (\mod 101) \text{ but 2n-1 is odd and 3 }\\
&= (-1)^k-1 (\mod 101) \text{ for some odd k}\\
&= -1 -1 (\mod 101)\\
&= -2 (\mod 101)
\end{align*}\)

Answer 53

this makes it more simple

Answer 54

thats kinda cute :D

Answer 55

:3

Answer 56

@Marki , nice ;) u are very good at mod properties

Answer 57

yeah ik im pure math genius :D

Answer 58

\(\large \tt \begin{align} \color{black}{\implies \frac{10^{12n-6}-1}{101}\\~\\
\implies \frac{100^{6n-3}-1}{101}\\~\\
\implies \frac{(101-1)^{6n-3}-1}{101}\\~\\
\implies \frac{(-1)^{6n-3}-1}{101}\\~\\
\implies \frac{(-1)^{-3}-1}{101}\\~\\
\implies \frac{-2}{101}\\~\\
\implies \frac{99}{101}\\~\\
\implies 99
}\end{align}\)

Answer 59

Neat :) binomial theorem will do !

Answer 60

Bravo :3

Answer 61

i was kind of stuck at -2 and forgot that it equals 99 ,lol

Answer 62

oh :D
the real challenge is to for the orginal problem that the mod is 1

Answer 63

show*

Answer 64

why do i feel, all of the @mathmath333 solution are similar :3 lol

Answer 65

mathmath style :S

Answer 66

well i have to say this for u hartnn when u dont understand things they will look like the same :P

Answer 67

cuz i didnt use the mod technique

but i basically learnt that to find remainders quickly
and i think it is optimal than it

Answer 68

he is biased to binomial thm like me and all other clever mathematicaians haha!

Answer 69

^

Answer 70

awwww xD

Answer 71

this is what i call applied :P

Answer 72

binomial theory rocks
mod technique s....nvm

Answer 73

:3
what i have to say 3 indians vs me

Answer 74

" mod arithmatic is universal"-ganeshie

Answer 75

mod/congruence theory is introduced by Gauss
and i feel it is just a neat way to use division algorithm

i thyink thats the reason the idea was rejected initially by math community.. i heard of this interesting story somewhere on youtube..xD

Answer 76

im Gaussian lover

Answer 77

yes division algorithm is general so mod arithmetic/congruences are also general
they make it more generic in group theory i think..

Answer 78

guys how about this idea?
\[\Large 101 \in \phi(\frac{ 10^{12n-1}-1 }{ 99 })\]
if we prove that then it gives us that 101 isn't a factor of that.

Answer 79

but phi Euler is very difficult XD

Answer 80

lol Gaussian lover ! it would have been tough for me to choose betwen euler and gauss if they were girls.. :P
Euler dude never rests. I think he shows up more frequently compared to gauss

Answer 81

Just \(\Large Fermet\) and \( \Large Euler \) XD

Answer 82

@PFEH.1999 for \(\large 10^{12n-6}-1 \pmod {99\cdot 101}\), try finding the order of \(10\) in \(\mod 99 \cdot 101\) by first finding \(\phi(99\cdot 101)\)

that works perfectly!

Answer 83

nice ;) will work on that...

Answer 84

well i love 10 per time :D
so its not a problem :3

Answer 85

oh lets see if phi works

Answer 86

it will work
thats how i would work when my brain doesn't work >.<

Answer 87

i have used it in your previous problem to prove 17 does not divide this number, right ?

Answer 88

10^phi(99.101)=1 mod 99.101
10^(6000)=1 mod (99.101)
eh yeah too easy :|

Answer 89

:D

Answer 90

i expected it to be so hard :D

Answer 91

@ganeshie8 <3 :*

Answer 92

13:13