1

Does the isbn detect jump transpositions?

$$a_1+2a_2+3a_3+\cdots+10a_{10}=0\pmod{11}$$

I think it does because the specific formula multiplying 1 times 1st digit, 2 times 2nd digit... will give you a remainder of zero if the isbn is correct. if it's not the right isbn, then you will get a remainder $\ge 1$.

vadim123
  • 82,796
user231623
  • 11
  • You've got the right general idea, now prove it! – vadim123 Apr 15 '15 at 13:33
  • Err that's where I get lost. So if, the nth digit is transposed with the (n+i)th digit, then unless n a sub (n+i) = (n+i) a sub n for some n in N, then the isbn is wrong. but this contradicts what i was trying to prove...? – user231623 Apr 15 '15 at 13:39

1 Answers1

0

Call the sum $a_1+2a_2+3a_3+\cdots+10a_{10}=S$. We have $S\equiv 0\pmod{11}$. Suppose we transpose the $i^\text{th}$ and $j^\text{th}$ digits. In order to not detect this transposition, we must have $$S-ia_i+ia_j-ja_j+ja_i\equiv 0\pmod{11}$$ We now remove $S$ (which is 0), and rearrange to get $$(j-i)a_i\equiv (j-i)a_j\pmod{11}$$

We now need one of the important properties of modular arithmetic:
If $ac\equiv bc\pmod{n}$ and $\gcd(c,n)=1$, then $a\equiv b\pmod{n}$

Since $11$ is prime, $i\neq j$, and $1\le i,j\le 10$, we know $\gcd(j-i,11)=1$. Hence we may conclude that $a_i\equiv a_j\pmod{11}$.

Hence the only transpositions we can't detect are of the same two digits transposed anyway.

vadim123
  • 82,796