Trololo

Algebra assignment 1.
Emil Nauerby.
20081332.
Let a be a number written (in base 10) as a0 · 100 + a1 · 101 + a2 · 102 − · · · +
an · 10n,
0 ≤ ai < 10.
1
Prove that 2 divides a if and only if 2 divides
a0.
1.1
2|a ⇒ 2|a0
2|a
⇒ [a]2 = 0 =
n
a
= [a
+
n
a
i=0
i · 10i 2
0]2
i=1
i · 10i 2
= [a
n
0]
+ 10 ·
n
a
= [a
+ [10]
a
2
i=1
i · 10i−1 2
0]2
2
i=1
i · 10i−1 2 2
= [a0] + 0 ·
n
a
= [a
+ 0 = [a
⇒ 2|a
2
i=1
i · 10i−1 2 2
0]2
0]2
0
1.2
2|a0 ⇒ 2|a
Let b be defined as follows:
n
b =
ai · 10i−1
i=1
Seeing how ai is a natural number ∀i, b is an integer number. It now follows
that
2|a0
⇒ [a0] = 0 = [a
+ [10 · b] .
2
0]2
2
since 10 · b is a multiple of 2.
[a0] + [10 · b]
= [a
2
2
0 + 10 · b]2
= a0 + a1 · 101 + a2 · 102 + · · · + an · 10n 2
= [a] = 0 ⇒ 2|a
2
1

---

2
Prove that 4 divides a if and only if a0 + 2a1
divides a.
2.1
4|a ⇒ 4|a0 + 2a1:
4|a
⇒ [a] = 0 =
n
a
= a
a
4
i=0
i · 10i 4
0 + a1 · 10 +
n
i=2
i · 10i 4
= a0 + a1 · 10 + 100 ·
n
a
i=2
i · 10i−2 4
= [a0 + a1 · 10] + 100 ·
n
a
4
i=2
i · 10i−2 4
= [a
n
0 + a1 · 10]
+ [100]
a
4
4
i=2
i · 10i−2 4 4
= [a0 + a1 · 10] + 0
n
a
4
i=2
i · 10i−2 2 4
= [a0 + a1 · 10] = [a
4
0 + a1 · (2 + 8)]4
= [a0] + [a
+ [a
= [a
4
1 · 2]4
1 · 8]4
0 + a1 · 2]4
⇒ 4|a0 + 2 · a1
2.2
4|a0 + 2a1 ⇒ 4|a:
4|a0 + 2a1
⇒ [a0 + 2 · a1] = 0 = [a
= [a
4
0 + (2 · 5) · a1]4
0 + a1 · 10]4
Since 4|100 it follows that [a0 + 10 · a1] +[100 · b] = [a
= 0
4
4
0 + 10 · a1 + 100 · b]4
if b is an integer number.
n
n
ai · 10i = 100 ·
ai · 10i−2
i=2
i=2
Since the expression above is a multiple of 100 it follows that
n
a0 + 10 · a1 + 100 ·
ai · 10i−2
= 0 = a0 + a1 · 101 + · · · + an · 10n 4
i=1
4
which implies 4|a.
3
Prove that 8 divides a if and only if 8 divides
a0 + 2a1 + 4a2:
3.1
8|a ⇒ 8|a0 + 2a1 + 4a2:
n
8|a ⇒ [a] = 0 = a
a
8
0 + 10a1 + 100a2 +
i · 10i
i=3
8
Since 8|1000 and
n
n
ai · 10i = 1000 ·
ai · 10i−3
i=3
i=3
2

---

is a multiple of 1000 it follows that
n
[a]
=
a
a
8
0 + 10ai + 100a2 + 1000 ·
i · 10i−3
i=3
8
n
=
[a0 + 10a1 + 100a2] + 1000 ·
a
8
i · 10i−3
i=3
8
=
[a0 + 10a1 + 100a2] = [a
8
0 + (2 + 8)a1 + (4 + 96)a2]8
Since 8|8 and 8|96 the above can be simplified as
[a0 + 2a1 + 4a2] = 0 ⇒ 8|a
8
0 + 2a1 + 4a2
3.2
8|a0 + 2a1 + 4a2 ⇒ 8|a:
8|a0 + 2a1 + 4a2
⇒
[a0 + 2a1 + 4a2] = 0
8
=
[a0 + (2 · 5)a1 + (4 · 25)a2]8
=
[a0 + 10a1 + 100a2]8
Since
n
1000 ·
ai · 10i−3
i=3
is a multiple of 1000 and 8|1000 it follows that
n
[a0 + 10a1 + 100a2] + 1000 ·
a
= 0
8
i · 10i−3
i=3
8
n
⇒
a0 + 10a1 + 100a2 + 1000 ·
ai · 10i−3
= [a] = 0
8
i=3
8
⇒
8|a
4
Prove that 5 divides a if and only if 5 divides
a0:
4.1
5|a ⇒ 5|a0:
n
n
5|a
⇒
[a] = 0 = a
a
= [a
+
a
5
0 +
i · 10i
0]5
i · 10i
i=1
5
i=1
5
Since
n
n
ai · 10i = 10 ·
ai · 10i−1
i=1
i=1
3

---

is a multiple of 10, it follows that
n
[a0] + 10 ·
a
=
[a
+ 0 = [a
5
i · 10i−1
0]5
0]5
i=1
5
⇒
5|a0
4.2
5|a0 ⇒ 5|a:
Since
n
10 ·
ai · 10i−1
i=1
is a multiple of 10 and 5|10 it follows that
n
[a0] + 10 ·
a
= 0
5
i · 10i−1
i=1
5
n
⇒
a0 + 10 ·
ai · 10i−1
= [a] ⇒ 5|a
5
i=1
5
5
Prove that 9 divides a if and only if 9 divides
the sum a0 + a1 + · · · + an of its digits.
n
5.1
9|a ⇒ 9|
ai
i=0
n
n
9|a
⇒
9|
ai · 10i ⇒
ai · 10i
= 0
i=0
i=0
9
Since (with integer i)
n
n
n
10i
=
10
=
[10]
=
1
= 1
9
9
i=1
9
i=1
9
i=1
9
it follows that
n
n
n
n
ai · 10i
=
ai · 10i
=
a
=
a
9
o · 1
i
i=0
9
i=0
9
i=0
9
i=0
9
4

---

n
5.2
9|
ai ⇒ 9|a:
i=0
n
n
n
 n
i−1

9|
ai ⇒
ai
= 0 =
ai
+ 
ai ·
9 · 10j 
i=0
i=0
9
i=0
9
i=1
j=1
9
i−1
since
9 · 10j is a multiple of 9. It then follows that
j=1
n
 n
i−1

n
ai
+
⇒

ai ·
9 · 10j  =
ai · 10i
= 0 = [a]
9|a
9
i=0
9
i=1
j=1
i=0
9
9
5

---