• :00Days
• :00Hours
• :00Mins
• 00Seconds
A new era for learning is coming soon

Suggested languages for you:

Americas

Europe

Q29E

Expert-verified
Found in: Page 255

### Discrete Mathematics and its Applications

Book edition 7th
Author(s) Kenneth H. Rosen
Pages 808 pages
ISBN 9780073383095

# Show that every positive integer can be represented uniquely as the sum of distinct powers of 2 . [Hint: Consider binary expansions of integers.]

Every positive integer can be represented uniquely as the sum of distinct powers

Of 2.

See the step by step solution

## Step 1

Let b be an integer greater than 1.

By theorem 1, every integer n can then be expressed uniquely in the form :

$n={a}_{n}{b}^{k}+{a}_{k-1}{b}^{k-1}+\dots +{a}_{1}b+{a}_{0}$

In this case , we have base 2. Thus there then exist unique values

such that :

$n={a}_{k}\cdot {2}^{k}+{a}_{k-1}\cdot {2}^{k-1}+\dots +{a}_{1}\cdot 2+{a}_{0}$

This then means that every positive integer n can be represented uniquely as the

sum of distinct powers of 2. Moreover, the coefficient ${a}_{k},{a}_{k-1},\dots ,{a}_{0}$ are given by the

binary representation of n .

## Step 2

When ${a}_{i}=1$ then x is first multiplied by the power and reduced modulo 645

Then on each iteration the power is multiplied by itself and reduced modulo 645.

$\mathrm{i}=0\text{since}{a}_{0}=0$

x = 1

$\text{power}={7}^{2}mod645=49mod645=49$

$\mathbf{i}=1{\text{Sincea}}_{1}=0:$

x = 1

$power={49}^{2}mod645=2401mod645=466\phantom{\rule{0ex}{0ex}}$

$\mathbf{i}=\mathbf{2}{\mathrm{Sincea}}_{2}=1$

$x=1.466=466$

$\text{power}={466}^{2}mod645=217156mod645=436$

$\mathbf{i}=\mathbf{3}{\mathrm{Sincea}}_{3}=0$

$x=466$

role="math" localid="1668514191719" $\text{power}={436}^{2}mod645=190096mod645=466$

$\mathbf{i}=\mathbf{5}{\text{Sincea}}_{5}=0$

$x=466\phantom{\rule{0ex}{0ex}}\phantom{\rule{0ex}{0ex}}\text{power}={436}^{2}mod645=190096mod645=466\phantom{\rule{0ex}{0ex}}\phantom{\rule{0ex}{0ex}}\mathbf{i}=\mathbf{6}{\text{Sincea}}_{6}=0\phantom{\rule{0ex}{0ex}}\phantom{\rule{0ex}{0ex}}x=466\phantom{\rule{0ex}{0ex}}\phantom{\rule{0ex}{0ex}}\text{power}={466}^{2}mod645=217156mod645=436$

## Step 3

$\mathbf{i}=7{\text{Since}}_{7}=1:\phantom{\rule{0ex}{0ex}}\phantom{\rule{0ex}{0ex}}x=466\cdot 436mod645=203176mod645=1\phantom{\rule{0ex}{0ex}}\phantom{\rule{0ex}{0ex}}\text{power}={436}^{2}\mathrm{mo}d645=190096mod645=466\phantom{\rule{0ex}{0ex}}\phantom{\rule{0ex}{0ex}}\mathbf{i}=\mathbf{8}{\text{Sincea}}_{8}=0:\phantom{\rule{0ex}{0ex}}\phantom{\rule{0ex}{0ex}}x=1\phantom{\rule{0ex}{0ex}}\phantom{\rule{0ex}{0ex}}\text{power}={466}^{2}mod645=217156mod645=436\phantom{\rule{0ex}{0ex}}\phantom{\rule{0ex}{0ex}}\mathbf{i}=9{\mathrm{sincea}}_{9}=1:\phantom{\rule{0ex}{0ex}}x=1.436mod645=436mod645=436\phantom{\rule{0ex}{0ex}}\phantom{\rule{0ex}{0ex}}\text{power}={436}^{2}mod645=190096mod645=466\phantom{\rule{0ex}{0ex}}\phantom{\rule{0ex}{0ex}}\text{return}x=436$