StudySmarter AI is coming soon!

- :00Days
- :00Hours
- :00Mins
- 00Seconds

A new era for learning is coming soonSign up for free

Suggested languages for you:

Americas

Europe

Q29E

Expert-verifiedFound in: Page 255

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.

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 .

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$

$\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$

94% of StudySmarter users get better grades.

Sign up for free