Show that ## 2^{n} ## divides an integer ## N ##.

  • Thread starter Math100
  • Start date
  • Tags
    Integer
In summary: N.In summary, the conversation discusses the criteria for an integer N to be divisible by 2^n, where n is the number of digits in N. The criteria states that 2^n divides N if and only if 2^n divides the number made up of the last n digits of N. This can be proven by induction, taking into consideration the increasing power of 10 for each additional digit in N. Both the direct and converse proofs are necessary to establish the equivalence.
  • #1
Math100
756
204
Homework Statement
Show that ## 2^{n} ## divides an integer ## N ## if and only if ## 2^{n} ## divides the number made up of the last ## n ## digits of ## N ##.
[Hint: ## 10^{k}=2^{k} 5^{k}\equiv 0\pmod {2^{n}} ## for ## k\geq n ##.]
Relevant Equations
None.
Proof:

Suppose ## 2^{n} ## divides an integer ## N ##.
Let ## N=a_{m}10^{m}+a_{m-1}10^{m-1}+\dotsb +a_{1}10+a_{0} ## for ## 0\leq a_{k}\leq 9 ##.
Then ## 2^{n}\mid N\implies 2^{n}\mid (a_{m}10^{m}+a_{m-1}10^{m-1}+\dotsb +a_{1}10+a_{0}) ##.
Note that ## 10^{k}=2^{k} 5^{k}\equiv 0\pmod {2^{n}} ## for ## k\geq n ##.
This means ## 2^{n}\mid 10^{n}\implies 2^{n}\mid (2^{n} 5^{n}) ##.
Thus
\begin{align*}
&2^{n}\mid [10^{n}(a_{n+i}10^{i}+\dotsb +a_{n}]\\
&2^{n}\mid (a_{n+i}10^{n+i}+\dotsb +a_{n}10^{n})\\
&2^{n}\mid (a_{n-1}10^{n-1}+\dotsb +a_{0}).\\
\end{align*}
Conversely, suppose ## 2^{n} ## divides the number made up of the last ## n ## digits of ## N ##.
Then ## 2^{n}\mid (a_{n-1}10^{n-1}+\dotsb +a_{0}) ##.
This means ## a_{n+i}10^{n+i}+\dotsb +a_{n}10^{n}=10^{n}(a_{n+j}10^{j}+\dotsb +a_{n})=2^{n} 5^{n}(a_{n+j}10^{j}+\dotsb +a_{n}) ##.
Thus
\begin{align*}
&2^{n}\mid (a_{n+i}10^{n+i}+\dotsb +a_{n}10^{n})\\
&2^{n}\mid (a_{n+i}10^{n+i}+\dotsb +a_{n-1}10^{n-1}+\dotsb +a_{n}10^{n})\\
&2^{n}\mid N.\\
\end{align*}
Therefore, ## 2^{n} ## divides an integer ## N ## if and only if ## 2^{n} ## divides the number made up of the last ## n ## digits of ## N ##.
 
Physics news on Phys.org
  • #2
How do we know that ##N## has ##n## digits? ##2^3\,|\,16## but ##16## has only ##2## digits. How can your criteria be an equivalence?

Let us assume ##N## has ##m## digits and ##n\leq m.##

Math100 said:
Thus
\begin{align*}
&2^{n}\mid [10^{n}(a_{n+i}10^{i}+\dotsb +a_{n}]\\
&2^{n}\mid (a_{n+i}10^{n+i}+\dotsb +a_{n}10^{n})\\
&2^{n}\mid (a_{n-1}10^{n-1}+\dotsb +a_{0}).\\
\end{align*}
Here, I got lost. What is i? You have to define the variables that you use. You also made a counting error.

We have ##m\geq n## and also ##2^m\geq 2^n.## Now ##N= (a_{m}10^{m}+a_{m-1}10^{m-1}+\dotsb +a_{n+1}10^{n+1}+a_n 10^n)+(a_{n-1}10^{n-1}+a_{n-2}10^{n-2}+\dotsb +a_{1}10+a_{0}).## From ##2^{m}\geq 2^n## we get ##2^n\,|\,10^n,10^{n+1},10^{n+2},\ldots,10^m## so ##N\equiv (a_{n}10^{n}+a_{n-1}10^{n-1}+\dotsb +a_{1}10+a_{0}) \pmod{2^n}.##

This is already what we have to show.

Remark:
If ##2^n\,|\,N## then ##0\equiv N\equiv (a_{n}10^{n}+a_{n-1}10^{n-1}+\dotsb +a_{1}10+a_{0}) \pmod{2^n}.##

If ##2^n\,|\, (a_{n}10^{n}+a_{n-1}10^{n-1}+\dotsb +a_{1}10+a_{0}) \pmod{2^n}## then ##N\equiv (a_{n}10^{n}+a_{n-1}10^{n-1}+\dotsb +a_{1}10+a_{0}) \equiv 0 \pmod{2^n}.##

The zero is on the left in one direction and on the right in the other direction.
Math100 said:
Conversely, suppose ## 2^{n} ## divides the number made up of the last ## n ## digits of ## N ##.
Then ## 2^{n}\mid (a_{n-1}10^{n-1}+\dotsb +a_{0}) ##.
This means ## a_{n+i}10^{n+i}+\dotsb +a_{n}10^{n}=10^{n}(a_{n+j}10^{j}+\dotsb +a_{n})=2^{n} 5^{n}(a_{n+j}10^{j}+\dotsb +a_{n}) ##.
Thus
\begin{align*}
&2^{n}\mid (a_{n+i}10^{n+i}+\dotsb +a_{n}10^{n})\\
&2^{n}\mid (a_{n+i}10^{n+i}+\dotsb +a_{n-1}10^{n-1}+\dotsb +a_{n}10^{n})\\
&2^{n}\mid N.\\
\end{align*}
Therefore, ## 2^{n} ## divides an integer ## N ## if and only if ## 2^{n} ## divides the number made up of the last ## n ## digits of ## N ##.
 
  • Like
Likes Math100
  • #3
fresh_42 said:
How do we know that ##N## has ##n## digits? ##2^3\,|\,16## but ##16## has only ##2## digits. How can your criteria be an equivalence?

Let us assume ##N## has ##m## digits and ##n\leq m.##Here, I got lost. What is i? You have to define the variables that you use. You also made a counting error.

We have ##m\geq n## and also ##2^m\geq 2^n.## Now ##N= (a_{m}10^{m}+a_{m-1}10^{m-1}+\dotsb +a_{n+1}10^{n+1}+a_n 10^n)+(a_{n-1}10^{n-1}+a_{n-2}10^{n-2}+\dotsb +a_{1}10+a_{0}).## From ##2^{m}\geq 2^n## we get ##2^n\,|\,10^n,10^{n+1},10^{n+2},\ldots,10^m## so ##N\equiv (a_{n}10^{n}+a_{n-1}10^{n-1}+\dotsb +a_{1}10+a_{0}) \pmod{2^n}.##

This is already what we have to show.

Remark:
If ##2^n\,|\,N## then ##0\equiv N\equiv (a_{n}10^{n}+a_{n-1}10^{n-1}+\dotsb +a_{1}10+a_{0}) \pmod{2^n}.##

If ##2^n\,|\, (a_{n}10^{n}+a_{n-1}10^{n-1}+\dotsb +a_{1}10+a_{0}) \pmod{2^n}## then ##N\equiv (a_{n}10^{n}+a_{n-1}10^{n-1}+\dotsb +a_{1}10+a_{0}) \equiv 0 \pmod{2^n}.##

The zero is on the left in one direction and on the right in the other direction.
I forgot to quantify the variable ## i ##.
 
  • #4
Math100 said:
I forgot to quantify the variable ## i ##.
I assume ##m=n+i## and ##j=i.## It was already late over here and I'm a bit tired. Guess I have been a bit harsher than necessary, sorry. Your proof looks ok except for the counting error. The last ##n## digits are ##a_{n-1},a_{n-2},\ldots,a_1,a_0.##
 
  • Like
Likes Math100
  • #5
@Math100, here are some ideas to think about.
If n = 1, ##2^n = 2^1 = 2## has to divide only the last digit, call it ##d_0##. That's trivial, since if 2 divides the last digit, the number N is even.
If n = 2, ##2^n = 2^2 = 4## has to divide the last two digits, ##d_1d_0##. This means that ##d^2##, if there is such a digit in N, is in the hundreds' place. 4 divides ##d_2 \times 100##, so if 4 also divides ##d_1d_0##, 4 also divides N.
And so on, which I leave to you. Each larger value of n corresponds to a higher power of 10, which has another factor of 2. A proof by induction might be appropriate here.

Keep in mind that this is an "if and only if" type of proof, so you have to also prove the converse. I.e., you need to prove that if ##2^n## divides the last n digits of N, then ##2^n## divides N, and if ##2^n## divides N, then ##2^n## divides the last n digits of N.
 
  • #6
fresh_42 said:
How do we know that ##N## has ##n## digits? ##2^3\,|\,16## but ##16## has only ##2## digits. How can your criteria be an equivalence?

Let us assume ##N## has ##m## digits and ##n\leq m.##Here, I got lost. What is i? You have to define the variables that you use. You also made a counting error.

We have ##m\geq n## and also ##2^m\geq 2^n.## Now ##N= (a_{m}10^{m}+a_{m-1}10^{m-1}+\dotsb +a_{n+1}10^{n+1}+a_n 10^n)+(a_{n-1}10^{n-1}+a_{n-2}10^{n-2}+\dotsb +a_{1}10+a_{0}).## From ##2^{m}\geq 2^n## we get ##2^n\,|\,10^n,10^{n+1},10^{n+2},\ldots,10^m## so ##N\equiv (a_{n}10^{n}+a_{n-1}10^{n-1}+\dotsb +a_{1}10+a_{0}) \pmod{2^n}.##

This is already what we have to show.

Remark:
If ##2^n\,|\,N## then ##0\equiv N\equiv (a_{n}10^{n}+a_{n-1}10^{n-1}+\dotsb +a_{1}10+a_{0}) \pmod{2^n}.##

If ##2^n\,|\, (a_{n}10^{n}+a_{n-1}10^{n-1}+\dotsb +a_{1}10+a_{0}) \pmod{2^n}## then ##N\equiv (a_{n}10^{n}+a_{n-1}10^{n-1}+\dotsb +a_{1}10+a_{0}) \equiv 0 \pmod{2^n}.##

The zero is on the left in one direction and on the right in the other direction.
But for the second part of the proof which starts with 'Conversely...', how should I prove this? Starting out with ## 2^{n}\mid (a_{n}10^{n}+a_{n-1}10^{n-1}+\dotsb +a_{1}10+a_{0})\pmod {2^{n}} ##. At first, I thought that using the hint would be easier but you said that there are counting errors.
 
Last edited:
  • #7
Math100 said:
But for the second part of the proof which starts with 'Conversely...', how should I prove this? Starting out with ## 2^{n}\mid (a_{n}10^{n}+a_{n-1}10^{n-1}+\dotsb +a_{1}10+a_{0})\pmod {2^{n}} ##. At first, I thought that using the hint would be easier but you said that there are counting errors.
Your error is that you wrote ##a_n## but it should be ##a_{n-1}##.
$$|\{a_0,a_1,a_2,\ldots,a_{n-2},a_{n-1},a_n\}|=n+1\quad \; , \;\quad |\{a_0,a_1,a_2,\ldots,a_{n-2},a_{n-1}\}|=n$$
##n## digits means to stop at ##n-1## since we started counting at ##0.##
 
  • Like
Likes Math100

Related to Show that ## 2^{n} ## divides an integer ## N ##.

1. How do you prove that 2^n divides an integer N?

To prove that 2^n divides an integer N, you need to show that N is a multiple of 2^n. This means that N can be expressed as N = 2^n * k, where k is any integer. This shows that 2^n is a factor of N and therefore, 2^n divides N.

2. What is the significance of showing that 2^n divides an integer N?

Showing that 2^n divides an integer N is significant because it helps us understand the divisibility of numbers. It also helps in solving various mathematical problems and proofs involving integers and their factors.

3. Can any integer N be divided by 2^n?

No, not all integers can be divided by 2^n. For 2^n to divide an integer N, N must be a multiple of 2^n. This means that N must have 2^n as one of its factors.

4. How can you use mathematical induction to prove that 2^n divides an integer N?

Mathematical induction is a proof technique that involves proving a statement for a base case and then showing that if the statement is true for n, it is also true for n+1. To prove that 2^n divides an integer N using mathematical induction, we can show that it is true for a base case (usually n=1) and then use the induction hypothesis to show that it is true for n+1.

5. Can you provide an example of how to use the concept of 2^n dividing an integer N in a real-life scenario?

One example of using the concept of 2^n dividing an integer N in a real-life scenario is in computer science. In computer programming, binary numbers are used to represent data and instructions. Since binary numbers are based on powers of 2, the concept of 2^n dividing an integer N is essential in understanding how binary numbers work and how they can be manipulated to perform various operations.

Similar threads

  • Precalculus Mathematics Homework Help
Replies
3
Views
1K
  • Precalculus Mathematics Homework Help
Replies
1
Views
882
  • Precalculus Mathematics Homework Help
Replies
7
Views
1K
  • Precalculus Mathematics Homework Help
Replies
3
Views
719
  • Precalculus Mathematics Homework Help
Replies
2
Views
992
  • Precalculus Mathematics Homework Help
Replies
6
Views
1K
  • Precalculus Mathematics Homework Help
Replies
5
Views
1K
  • Precalculus Mathematics Homework Help
Replies
3
Views
847
  • Precalculus Mathematics Homework Help
Replies
5
Views
2K
  • Precalculus Mathematics Homework Help
Replies
2
Views
657
Back
Top