1
00:00:00,100 --> 00:00:04,400
Hello everyone, and welcome to this
week's Carmen's Core Concepts.

2
00:00:04,400 --> 00:00:07,000
This is week 2, my 
name is Carmen Bruni,

3
00:00:07,000 --> 00:00:09,300
and this week we're 
gonna talk about some

4
00:00:09,300 --> 00:00:11,800
of the key concepts that we 
did in Math 135 in week 2.

5
00:00:11,800 --> 00:00:14,633
Again, I want to remind you that
this isn't a substitute for lectures

6
00:00:14,633 --> 00:00:16,900
in any way, shape, or form. I'll 
be going way too quickly

7
00:00:16,900 --> 00:00:18,900
for this to be a 
substitute for lectures,

8
00:00:18,900 --> 00:00:22,433
but what this is supposed to do is it's supposed 
to reinforce the key ideas of the week

9
00:00:22,433 --> 00:00:24,266
to give you an idea 
of what we did

10
00:00:24,266 --> 00:00:27,000
and to be used in conjunction 
with other tools,

11
00:00:27,000 --> 00:00:30,333
like going to lectures, like
practicing the problems, etc etc.

12
00:00:30,333 --> 00:00:30,366


13
00:00:30,366 --> 00:00:32,666
So let's start with 
divisibility theorems.

14
00:00:32,666 --> 00:00:35,466
So last week we finished off 
with Bounds By Divisibility,

15
00:00:35,466 --> 00:00:37,533
this week we'll start with it and 
talk about a couple of others.

16
00:00:37,533 --> 00:00:38,866
So let a, b, c 
be integers,

17
00:00:38,866 --> 00:00:40,833
recall that Bounds By
Divisibility states that

18
00:00:40,833 --> 00:00:42,433
"if a divides b
and b is non-zero,

19
00:00:42,433 --> 00:00:45,300
then the magnitude of a is less than 
or equal to the magnitude of b."

20
00:00:45,300 --> 00:00:48,133
So it gives us a bound 
on the size of a and b.

21
00:00:48,133 --> 00:00:49,866
So if a and b are always
positive, then

22
00:00:49,866 --> 00:00:52,633
a must be less than or
equal to b, if it divides...

23
00:00:52,633 --> 00:00:54,966
if a divides b,
for example.

24
00:00:54,966 --> 00:00:57,466
Transitivity of Divisibility, 
so we call this TD.

25
00:00:57,466 --> 00:01:01,900
Transitivity itself is a very important 
mathematical concept. It's

26
00:01:01,900 --> 00:01:05,500
one of the conditions to be an
equivalence relation, for example.

27
00:01:05,500 --> 00:01:07,400
So we'll see 
it again later.

28
00:01:07,400 --> 00:01:09,233
What do we have
here? We have

29
00:01:09,233 --> 00:01:12,700
a divides b and b divides c and 
that implies that a divides c,

30
00:01:12,700 --> 00:01:15,000
so the transitivity part is if 
the middle thing is the same,

31
00:01:15,000 --> 00:01:17,366
so in this case the 
b on either side, 

32
00:01:17,366 --> 00:01:20,066
and a divides b and b divides 
c, then a must divide c.

33
00:01:20,066 --> 00:01:22,666
This can be…you can change 
divisibility with, let's say "equals",

34
00:01:22,666 --> 00:01:24,433
or other operators 
that you know.

35
00:01:24,433 --> 00:01:26,266
So many things 
are transitive.

36
00:01:26,266 --> 00:01:29,933
Divisibility of Integer Combinations, 
one of the

37
00:01:29,933 --> 00:01:32,666
most used theorems 
of this course.

38
00:01:32,666 --> 00:01:34,633
If a divides b 
and a divide c,

39
00:01:34,633 --> 00:01:37,866
then for all x and y 
inside the integers,

40
00:01:37,866 --> 00:01:39,866
a divides b x
plus c [y].

41
00:01:39,866 --> 00:01:42,766
So we'll talk about “for all” a
little bit more in depth later, but

42
00:01:42,766 --> 00:01:45,566
I just want to use this symbol here 
just to show that you can write

43
00:01:45,566 --> 00:01:47,433
DIC using
just symbols.

44
00:01:47,433 --> 00:01:51,100
The proof of DIC it’s, again, one of these 
“follow your nose” type of proofs I like to say.

45
00:01:51,100 --> 00:01:53,300
Assume the hypothesis, 
and then it kind of just

46
00:01:53,300 --> 00:01:55,933
gradually leads you 
towards the conclusion.

47
00:01:55,933 --> 00:01:58,733
At this point in the course, we 
really don't have any tools so

48
00:01:58,733 --> 00:02:01,166
if all you get is a divides 
b and a divides c,

49
00:02:01,166 --> 00:02:03,233
you probably want 
to use the definition.

50
00:02:03,233 --> 00:02:04,266


51
00:02:04,266 --> 00:02:08,600
Using the definition gives you integers m and 
n such that a m equals b and a n equals c,

52
00:02:08,600 --> 00:02:11,366
and then for any integers
x and y, we have that

53
00:02:11,366 --> 00:02:14,600
b x plus c y is equal to 
a times some integer,

54
00:02:14,600 --> 00:02:17,300
and hence, a divides 
b x plus c y.

55
00:02:17,300 --> 00:02:19,166
So the proof, again, is a “follow 
your nose” kind of proof.

56
00:02:19,166 --> 00:02:20,800
It's very short, 
very sweet,

57
00:02:20,800 --> 00:02:25,300
but this property here, this theorem,
has a lot of applications.

58
00:02:25,300 --> 00:02:27,200
Let's see an 
example of them.

59
00:02:27,200 --> 00:02:28,066


60
00:02:28,066 --> 00:02:30,033
Here's just one example 
of applying it, 

61
00:02:30,033 --> 00:02:33,300
so if 5 divides a plus 2b 
and 5 divides 2a plus b,

62
00:02:33,300 --> 00:02:36,366
then 5 divides… 
well if I take

63
00:02:36,366 --> 00:02:38,566
2 times the 
first term,

64
00:02:38,566 --> 00:02:42,333
and and add negative 1 
times the second term,

65
00:02:42,333 --> 00:02:44,600
then it divides that. 
Well what is that?

66
00:02:44,600 --> 00:02:47,966
Well it's 2a plus 4b 
minus 2a minus b,

67
00:02:47,966 --> 00:02:50,933
the two a’s are gonna cancel and 
you’re gonna be left with 3b.

68
00:02:50,933 --> 00:02:54,200
So this shows you a way that you can 
use Divisibility of Integer Combinations

69
00:02:54,200 --> 00:02:57,133
to find integer combinations 
to get things like…

70
00:02:57,133 --> 00:02:59,900
so to get rid of a variable, for 
example, so here we got rid of a,

71
00:02:59,900 --> 00:03:02,733
you can use them prove 
all sorts of things.

72
00:03:02,733 --> 00:03:05,700
Proving that big numbers are divisible
if you know that smaller numbers are,

73
00:03:05,700 --> 00:03:07,700
so you can combine them 
to make bigger numbers

74
00:03:07,700 --> 00:03:09,300
that are divisible by 
certain numbers. 

75
00:03:09,300 --> 00:03:11,300
Lots of interesting 
applications of DIC.

76
00:03:11,300 --> 00:03:13,566
Again, we're gonna see this
throughout the course,

77
00:03:13,566 --> 00:03:16,100
so it is worth its own slide 
to give an example.

78
00:03:16,100 --> 00:03:18,800
Very short, but it 
is a core concept

79
00:03:18,800 --> 00:03:23,766
and you really should try to 
understand DIC in its fullness.

80
00:03:23,766 --> 00:03:25,300


81
00:03:25,300 --> 00:03:28,466
Converses, so next
week especially

82
00:03:28,466 --> 00:03:31,033
we're going to see a lot of words 
that begin with the letter C,

83
00:03:31,033 --> 00:03:33,466
and it's very easy to get 
them confused, so

84
00:03:33,466 --> 00:03:35,833
now is a good time that 
we just have this one

85
00:03:35,833 --> 00:03:39,700
to put it in your memory banks and make 
sure that you have it down solid.

86
00:03:39,700 --> 00:03:41,433
Let A and B 
be statements.

87
00:03:41,433 --> 00:03:44,700
the converse of A implies 
B is B implies A.

88
00:03:44,700 --> 00:03:46,900
So hypothesis implies 
conclusion,

89
00:03:46,900 --> 00:03:49,300
the converse is conclusion 
implies hypothesis.

90
00:03:49,300 --> 00:03:51,566
A very simple definition.

91
00:03:51,566 --> 00:03:54,500
Converses are useful 
in mathematics.

92
00:03:54,500 --> 00:03:56,766
If you prove an implication 
and you prove its converse,

93
00:03:56,766 --> 00:03:59,766
that's much stronger than
just proving an implication itself.

94
00:03:59,766 --> 00:04:03,433
It somehow gives you a 
classification-type theorem,

95
00:04:03,433 --> 00:04:06,366
which is a lot stronger 
than just an implication.

96
00:04:06,366 --> 00:04:09,300
So as an example, the converse 
of Bounds By Divisibility

97
00:04:09,300 --> 00:04:10,966
is given by,

98
00:04:10,966 --> 00:04:13,300
“if the absolute value of a is less than 
or equal to the absolute value of b,

99
00:04:13,300 --> 00:04:17,866
then a divides b and 
b does not equal 0."

100
00:04:17,866 --> 00:04:21,300
Notice that 
this is false.

101
00:04:21,300 --> 00:04:24,166
There's many counter 
examples of this,

102
00:04:24,166 --> 00:04:27,466
so I mean, just take a equals 6 
and b equals 7, for example.

103
00:04:27,466 --> 00:04:30,833
6 is less than 7 but clearly 
6 does not divide 7.

104
00:04:30,833 --> 00:04:33,300


105
00:04:33,300 --> 00:04:37,300
There are plenty of examples 
where this can go awry.

106
00:04:37,300 --> 00:04:39,300


107
00:04:39,300 --> 00:04:41,666
Okay, that's all I really want
to say about converses.

108
00:04:41,666 --> 00:04:45,600
But we can use converses in the 
next topic which is “if and only if” 

109
00:04:45,600 --> 00:04:46,900
statements.

110
00:04:46,900 --> 00:04:48,866
So again, let A and 
B be statements.

111
00:04:48,866 --> 00:04:51,100
we defined “if and only 
if”… so A if and only if B

112
00:04:51,100 --> 00:04:53,000
we defined it 
by a truth table.

113
00:04:53,000 --> 00:04:56,300
Here we said A if
and only if B is true

114
00:04:56,300 --> 00:05:00,233
if and only if both A and B are true or 
false, so they share the same value.

115
00:05:00,233 --> 00:05:03,133
So if A and B share the 
same truth or false value,

116
00:05:03,133 --> 00:05:07,700
then we say that A if and only if B 
is true, and otherwise it's false.

117
00:05:07,700 --> 00:05:09,066


118
00:05:09,066 --> 00:05:11,166
So how do we prove 'if and 
only if' questions in practice?

119
00:05:11,166 --> 00:05:13,066
This exercise is what
actually shows it.

120
00:05:13,066 --> 00:05:15,166
I'm not going to prove it, I 
didn’t prove it in class either,

121
00:05:15,166 --> 00:05:17,733
“Show that A if and only if B is
logically equivalent to

122
00:05:17,733 --> 00:05:20,266
A implies B ‘and’
B implies A.”

123
00:05:20,266 --> 00:05:22,066
That's something I'll 
leave as an exercise.

124
00:05:22,066 --> 00:05:24,133
But this gives you an
idea of how to prove it.

125
00:05:24,133 --> 00:05:27,100
Well  you prove the normal 
thing, you prove

126
00:05:27,100 --> 00:05:29,000
the implication 
A implies B,

127
00:05:29,000 --> 00:05:30,933
and then you prove 
its converse.

128
00:05:30,933 --> 00:05:33,033
So if an implication and its 
converse are true, then

129
00:05:33,033 --> 00:05:35,566
the statement is an ‘if 
and only if’ statement. 

130
00:05:35,566 --> 00:05:39,333
We'll see a practical example 
of ‘if and only if’s

131
00:05:39,333 --> 00:05:42,766
when we deal with sets afterwards. 
I wanted to say that to

132
00:05:42,766 --> 00:05:46,400
accumulate everything; 
to give a nice

133
00:05:46,400 --> 00:05:48,166
bridge between 
the two topics.

134
00:05:48,166 --> 00:05:50,966
But that basically covers the end 
of the first lecture of the week.