We will guide you through a a proof of Lucas' Theorem. This theorem states that
(
n
k
)
(
k
n
)start binomial, left parenthesis, n, over, k, right parenthesis, end binomial is odd if
(
k
)
i
≤
(
n
)
i
(k)
i
≤(n)
i
left parenthesis, k, right parenthesis, start subscript, i, end subscript, is less than or equal to, left parenthesis, n, right parenthesis, start subscript, i, end subscript for all and even otherwise. Here,
(
n
)
i
(n)
i
left parenthesis, n, right parenthesis, start subscript, i, end subscript is the
i
ii-th least significant bit of
n
nn if written in binary. For example,
11
1111 in binary is
1011
10111011 and
3
33 is
11
1111 (or
0011
00110011 to make sure that both have four bits). Now
0011
00110011 is ``bitwise at most''
1011
10111011, and thus Lucas' Theorem states that
(
11
3
)
(
3
11
)start binomial, left parenthesis, 11, over, 3, right parenthesis, end binomial is odd. Which it is, since
(
11
3
)
=
165
(
3
11
)=165start binomial, left parenthesis, 11, over, 3, right parenthesis, end binomial, equals, 165.
To get started, let us introduce some notation. For an integer
n
≥
1
n≥1n, is greater than or equal to, 1 we define
f
(
n
)
:
=
max
{
k
∈
N
0
such that
2
k
divides
n
}
f(n):=max{k∈N
0
such that 2
k
divides n}f, left parenthesis, n, right parenthesis, colon, equals, \max, left brace, k, \in, N, start subscript, 0, end subscript, space, start text, s, u, c, h, space, t, h, a, t, end text, space, 2, start superscript, k, end superscript, start text, space, d, i, v, i, d, e, s, space, end text, n, right brace. For example,
f
(
5
)
=
0
f(5)=0f, left parenthesis, 5, right parenthesis, equals, 0,
f
(
14
)
=
1
f(14)=1f, left parenthesis, 14, right parenthesis, equals, 1,
f
(
12
)
=
2
f(12)=2f, left parenthesis, 12, right parenthesis, equals, 2.
Let
n
:
=
1000101010101010100001010101011111100110100000
n:=1000101010101010100001010101011111100110100000n, colon, equals, 1000101010101010100001010101011111100110100000, where this is to be read in binary. What is
f
(
n
)
f(n)f, left parenthesis, n, right parenthesis?
MathBot Answer:
MathBot is working on a solution to your problem.
