text:
# Recommendations about modifying usage of built-in symbols

In my package, I use some of the built-in Mathematica symbols in non-canonical ways. Right now, I use them as Options or OptionValues to certain package symbols. Therefore, I modified the ::usage of the built-in symbols to include information about how those symbols are used in the package.

For example the package has a function FoldDistribution and I've given it an option Integer that can be True or False. So I modified the ::usage as follows:

Unprotect[Integer]

Integer::usage = "Integer is the head used for integer.
Integer is an option to FoldDistribution."

Protect[Integer]

Giving ? Integer:

So far, things look like they're going ok, and nothing fundamentally wrong seems to be happening with how Mathematica operates. Question: should I be worried about anything bad happening down the line? Is it recommended not to use built-in symbols in unintended ways? And what about changing their usage messages?

• Built-ins are not bound by the same rules as top-level definitions. Do not be surprised if your modifications magically disappear at any time during a session, or are accepted in some contexts but ignored in others. Personally, I would never do this in a package. – Oleksandr R. Dec 20 '15 at 22:41
• I also think this might be error prone. But at a design level, why do you have a need to use that particular name for an option? And if it is absolutely the only name that makes sense, why not go with the string "Integer"? – Daniel Lichtblau Dec 20 '15 at 23:51
• I second the concerns of others. I would never do this. Use your own names or strings, as others have suggested. Changing properties of built-in symbols have an effect on entire system, and you can't know all the consequences. There have been multiple discussions about this here on the site, notably this one, and also here. You can seldom win big by changing built-ins, but it is very easy to mess things up badly. – Leonid Shifrin Dec 21 '15 at 8:12
• @LeonidShifrin Thanks. The answer by Istvan seems to disagree with your opinion. Perhaps I should have mentioned that the only way I intend to use the symbols are as option names. I don't modify their definitions. Would this be safe? Or would still advise against it? – QuantumDot Dec 21 '15 at 21:00
• @IstvánZachar I would still not do this. I do sometimes use built-ins as option names, but usually as a short-cut, and I never document that (so never really modify those symbols' global properties). And I would never do anything like that in the user-facing code. Any global modification you make to a built-in symbol, can have unanticipated consequences. And the more common the symbol is, the bigger are the chances to mess something up. Given other possibilities (your own names or strings), I just don't see that the the gain is worth the risk. – Leonid Shifrin Dec 22 '15 at 5:16

You don't have to unprotect system symbols to attach messages to them. The usual way (used throughout built-in packages) is the following way:

Attributes[Dot]
Message[Dot::usage]

Dot::usage = If[ValueQ[Dot::usage], Dot::usage <> "\n" <> #, #] &@ "MyFunction[..., Dot -> ...] does ...";
Message[Dot::usage]

As long as you use the symbol only as an inert option name I think this is a pretty safe method, as you do not even unprotect it so you cannot mess up its definition.

Note, that if you call the attaching code a second time, you will have a redundant message: make sure that you package this so that it is only called once. The ValueQ thing is only needed if you attach to a symbol that you are not sure is defined in another package, not being a system symbol.

• It's good to know I don't need to unprotect the system symbol to attach messages to them. And yes, it is true the only way I'm using these symbols are as option names. So I suppose you would disagree with the comments under the original question provided I only use these symbols as options names? – QuantumDot Dec 21 '15 at 20:58
• @QuantumDot Exactly. I'm using this kind of extension since years and without any problem. I do not like to clutter the namespace with extra symbolnames, and on top of that, I do not like to use MyIntegrate as an option name when Integrate describes the best what my option does. Let's be honest, Stephen Wolfram really put a lot of thought into naming things and he did a quite good job. On the other hand, he really forced us to come up with convoluted names if we do not want interference. – István Zachar Dec 21 '15 at 21:31
• I will accept this answer, also bearing in mind the warnings given by Leonid and Daniel as comments to the question. – QuantumDot Dec 26 '15 at 22:09

format: plain


text:
# Homework Help: Volume of the space region inside sphere outside coni

1. May 13, 2012

### melihaltintas

1. The problem statement, all variables and given/known data

2. Relevant equations
volume of the space region inside sphere outside coni
z^2=x^2+y^2 coni
x^2+y^2+z^2 =1 sphere

3. The attempt at a solution
I am new in this forum , I search question like this and i found but i didn't solve this question with method that is performed other questions

2. May 13, 2012

### sharks

Hi melihaltintas

First, always plot the graph so you can understand how to find the limits.

I have attached the graph of the xz-trace coordinates (in the plane y = 0). The region of volume that you need to find is shaded in blue.

Start by finding the points of intersection of the sphere and cones (in the plane y = 0).

Your equations for the cones and sphere in the plane y = 0, become:
$$z^2=x^2 \\x^2+z^2 =1$$
Solve these two equations to find the x and z. From there, you'll be able to find the two required angles for $\phi$ which define the limits.

Finally, use the triple integral formula in terms of spherical coordinates:
$$\int \int \int \rho^2 \sin \phi d\rho d\phi d\theta$$

#### Attached Files:

• ###### xz.gif
File size:
5.9 KB
Views:
145
Last edited: May 13, 2012
3. May 13, 2012

### melihaltintas

thanks a lot :)


text:
Voltage Across Capacitor

Homework Statement

[PLAIN]http://img189.imageshack.us/img189/4555/capacitorh.jpg [Broken]

Homework Equations

$I(t)=I_0 e^{-t/\tau}$ (current as a function of time for a capacitor being charged)

The Attempt at a Solution

The time constant of the circuit is τ=RC=7s. And the initial current in the circuit is

v/Req=300/1489=0.2A (I know this is correct)

Now pluging into the equation:

$I(5)=0.2 e^{-5/7}=0.0979 \ A$

$V=IR= 0.0979 \ A \times 1489 \Omega = 145.73 \ V$

But the correct solution must be 153V. I'm very confused, what's wrong with my working?

Last edited by a moderator:


text:
# aceplot

aceplot produces the aceplot to visualize the results of ace

## Syntax

• aceplot(out)example
• aceplot(out,Name,Value)example

## Description

This function produces two figures. The first figure contains a series of panels for transformed X_j vs. X_j (with a rug plot long the tick marks), while the second figure contains: the plot of transformed y vs.

y, the plot of residuals vs. fit and the plot of transformed y vs. fit.

 aceplot(out) Example of the use of ace based on the Wang and Murphy data.

 aceplot(out, Name, Value)

## Examples

expand all

### Example of the use of ace based on the Wang and Murphy data.

In order to have the possibility of replicating the results in R using library acepack function mtR is used to generate the random data.

rng('default')
seed=11;
negstate=-30;
n=200;
X1 = mtR(n,0,seed)*2-1;
X2 = mtR(n,0,negstate)*2-1;
X3 = mtR(n,0,negstate)*2-1;
X4 = mtR(n,0,negstate)*2-1;
res=mtR(n,1,negstate);
% Generate y
y = log(4 + sin(3*X1) + abs(X2) + X3.^2 + X4 + .1*res );
X = [X1 X2 X3 X4];
% Apply the ace algorithm
out= ace(y,X);
% Show the output graphically using function aceplot
aceplot(out)

## Input Arguments

### out — Structure containing the output coming from ace procedure. Structure.

Structure containing the following fields.

Value Description
ty

n x 1 vector containing the transformed y values.

tX

n x p matrix containing the transformed X matrix.

rsq

the multiple R-squared value for the transformed values in the last iteration of the outer loop.

y

n x 1 vector containing the original y values.

X

n x p matrix containing the original X matrix.

Data Types: struct

### Name-Value Pair Arguments

Specify optional comma-separated pairs of Name,Value arguments. Name is the argument name and Value is the corresponding value. Name must appear inside single quotes (' '). You can specify several name and value pair arguments in any order as  Name1,Value1,...,NameN,ValueN.

Example:  'highlight',1:10 , 'plots', [-3 3; -2 2; -2 2]

### highlight —units to highliight in the plot.vector.

Vector contaning the numbers associate to the units to highlight in the plots.

Example:  'highlight',1:10

Data Types: double

### ylimy —2D array of size 3-by-2 which specifies the lower and upper limits for the 3 plots of the second figure.the first row refers to the plot of transformed y vs.

y, the second row refers to the plot of residuals vs.

fit and the third row to the the plot of transformed y vs.

fit. The default value of ylimy is [], that is automtic scale is used.

Example:  'plots', [-3 3; -2 2; -2 2]

Data Types: single | double

## References

Breiman, L. and Friedman, J.H. (1985), Estimating optimal transformations for multiple regression and correlation, "Journal of the American Statistical Association", Vol. 80, pp. 580-597.

Wang D. and Murphy M. (2005), Identifying nonlinear relationships regression using the ACE algorithm, "Journal of Applied Statistics", Vol. 32, pp. 243-258.


text:
# Checking if a symbolic matrix is positive semi-definite

As far as I can tell, there is no way to tell the builtin PositiveSemidefiniteQ about assumptions on symbols.

For example, the matrix

{{1,0,0,Sqrt[1-p]}, {0,0,0,0}, {0,0,p,0}, {Sqrt[1-p],0,0,1-p}}

has eigenvalues {0,0,2-p,p} and is therefore positive semi-definite whenever 0<=p<=2, but PositiveSemidefiniteQ always returns False.

Is checking the non-negativity of the eigenvalues with \$Assumptions a good way to test for this? Or would it be better to do something like row-reduction? There are a bunch of algorithms answering this related question, but I don't know which ones translate best to symbolics.

Edits:

1. The scope section of the documentation for PositiveSemidefiniteQ says "The test returns False unless it is true for all possible complex values of symbolic parameters")
2. For clarification, I mean my questions exactly as stated above. To paraphrase, what is the best way to check for the positive semi-definite condition of a symbolic matrix allowing for symbol assumptions? This question is given in the context that, in the numeric case, checking eigenvalue signs is not the best way.
• "I am therefore interested in an implementation that allows for assumptions." <-- I would recommend rewriting your question, including this bit of information I found, and asking specifically about such an implementation. I deleted my answer to give room for new ones. For reference, my answer pointed at the documentation of PositiveDefiniteMatrixQ, Examples -> Scope. Apr 15, 2015 at 19:57

One way is shown below. Alternatives include using Simplify with Assumptions, again on testing that the eigenvalues are nonnegative.
Resolve[


text:
# Calculating income-expenditure multiplier?

If planned aggregate expenditure in an economy can be written as: PAE = 5000 + 0.8Y, what is the income-expenditure multiplier in this economy?

My Attempt:

Y = 5000 + 0.8Y
Y - 0.8Y = 5000
0.2Y = 5000
Y = 25000

Since the marginal propensity to consume (MPC) is equal to ΔC / ΔY, where ΔC is change in consumption, and ΔY is change in income.

25000 / 20000 = 1.25

Do I take this further using multiplier = 1 / (1 - MPC) = 1 / (1-1.25) = 4

No, that is not correct. In the Keynesian model, the only variable that reacts to output is consumption. Other components of the aggregate demand do not.

For instance, in a closed economy, aggregate demand is $C+G+I$. Here, $C=c_0 + c_1Y$, where $c_0$ is autonomous consumption and $c_1$ is the MPC.

Hence, planned expenditure is

$$Y^e = c_0 + G + I + c_1Y$$

which can be condensed to

$$Y^e = a + bY$$

This is the equation you are given. Thus, the MPC is 0.8. This is actually the slope of the PAE curve in the Keynesian Cross diagram. It is usually lower than one. Calculation of the multiplier goes as normal.


text:
# Uniqueness results for inverse Sturm-Liouville problems with partial information given on the potential and spectral data

Research paper by Zhaoying Wei, Guangsheng Wei

Indexed on: 11 Nov '16Published on: 11 Nov '16Published in: Boundary Value Problems

#### Abstract

We consider the inverse spectral problem for a Sturm-Liouville problem on the unit interval $$[0,1]$$. We obtain some uniqueness results, which imply that the potential q can be completely determined even if only partial information is given on q together with partial information on the spectral data, consisting of the spectrum and normalizing constants. Moveover, we also investigate the problem of missing both eigenvalues and normalizing constants in the situation where the potential q is $$C^{2k-1}$$ near a suitable point.


text:
Run Jenkins Script Console Scripts from Command Line (Without Remoting)

If you’re like me, you generally enjoy using the command line, and want to make as much available to it as possible.

Jenkins has a decent CLI client, Jenkins CLI, that allows you to do a number of Jenkins things from the command line. It also seems to be steeped in history – at least judging from the number of deprecated protocols and options. The most relevant deprecation here is Remoting, which, among other things, allows the transfer of files to and from the server – so that is no longer possible. More on that later.

Setting up Jenkins CLI

Throughout this guide, replace my.jenkins.instance with the domain for your Jenkins instance.

curl 'https://my.jenkins.instance/jnlpJars/jenkins-cli.jar' > "$HOME/bin/jenkins-cli.jar" Next, to use the Jenkins CLI, you need a token to be able to log in. To get the token, log in to your Jenkins instance, go to your user’s dropdown in the top-right corner of the screen > Configure > Show API Token…. Copy the User ID and API Token in to the following command, replacing <User ID> and <API Token> respectively, which will put them in to a file we’ll use shortly: echo '<User ID>:<API Token>' > "$HOME/.jenkins-cli-auth"

You are now able to use the Jenkins CLI with your own commands!

java -jar "$HOME/bin/jenkins-cli.jar" -s 'https://my.jenkins.instance' -noKeyAuth -auth "@$HOME/.jenkins-cli-auth" <command...>

I recommend making an alias – future examples will use this alias:

jenkinsCli() {
java -jar "$HOME/bin/jenkins-cli.jar" -s 'https://my.jenkins.instance' -noKeyAuth -auth "@$HOME/.jenkins-cli-auth" "[email protected]"
}

Pro Tip: There’s nothing stopping you from downloading multiple JARs for different instances of Jenkins, and making multiple aliases to use them.

Getting an interactive shell

Once you have the CLI working, you can log on to Jenkins and get an interactive shell for scripting using:

jenkinsCli groovysh

For example, let’s say you want to clear the build queue of all of its jobs, something I’ve written about before. Entering the following code in to the shell will do that:

import jenkins.model.*
Jenkins.instance.queue.clear()

Note the import, which has been added to the code from the original post. This is because the web shell automatically imports import jenkins.model.* and import hudson.model.* for you, whereas the CLI’s interactive shell doesn’t. So we add it ourselves.

Running scripts from files without remoting

Now suppose that you like to clear the build queue quite regularly, and you get fed up of typing it or copying and pasting it. It is possible to place code in to re-usable scripts.

Following our example from earlier, let’s say we got fed up and copied the script (with imports) in to a new file, ~/jenkins-cli/clear-build-queue.groovy.

We can then run this script in Jenkins by running the following command:

jenkinsCli groovy = < ~/jenkins-cli/clear-build-queue.groovy

groovy is a subcommand that runs a Groovy script directly on the Jenkins master, without a wrapper shell. = instructs Jenkins CLI to expect stdin to provide a script to run. < feeds the contents of the Groovy file to jenkinsCli via stdin (where it is listening, thanks to =).

With that, you can now run scripts on Jenkins without leaving the comfort of your command line.

Currying vs Partial Function Application

While having a read in to the art of function programming, I stumbled upon a curious technicality. Those that know me know (perhaps wearily) I love talking about technical stuff.

Currying (wikipedia) builds a single function that, in effect, takes multiple arguments by composing a chain of functions that each take a single argument and eventually yield the final result:

f: (x, y, z) -> result
curry(f): x -> (y -> (z -> result))

So if you wanted to call a curried function, it would look something like:

f(first_arg)(second_arg)(third_arg)

Functional languages often compose multiple-argument functions using what appears to be currying.

But wait, that’s not what I just said! I must be an awful writer, spreading misinformation like that. After all, I’ve read plenty of blogs and articles that tell me that currying is where you “fix” some arguments in place ahead of final invocation. The result is creating a function with fewer arguments, like so:

f(x, y, z) -> result
g(z) -> f(1, 2, z)

It turns out that this is known as partial function application. How it came to be known as currying I am not sure, but it seems to be a very common misconception. I believed it too until recently! Yet another thing to remember.

Wikipedia contrasts currying and partial function application in detail if you want to compare them further.

Cancel All Queued Jenkins Jobs

I do not believe cancelling all queued Jenkins jobs is possible via the UI. Fortunately, it is possible if you have access to the Script Console.

Run this in Manage Jenkins > Script Console:

Jenkins.instance.queue.clear()

While this script is innocuous, always be careful when using the Script Console. Any script run inside it effectively has administrative permissions over Jenkins!

Update 2018-09-11: Use Jenkins instead of the deprecated Hudson.

Overview

Taking regular backups of important devices is sensible advice. And backups themselves are no good unless you can restore them. This guide gives a brief overview on how to backup and restore a stock Android device – that is, a device that runs an uncustomised version of Android, that is unrooted. It may also work for non-stock Android devices.

One big caveat: While this is the best method I have found without root, I have not had consistent results across devices when restoring backups, even among Nexus devices. So I recommend that this method is not relied upon exclusively for backup.

Usage information

We will be using adb backup and adb restore to backup and restore device state.

To find out usage information for your device, connect it and run:

This info was found by simply running adb.

This guide assumes the backup and restore commands work like stock Android devices.

Backup

1. Set up your computer and device so that your computer can access the device via USB. There are plenty of good guides out there, but in summary this’ll involve enabling USB debugging on the device and installing the Android SDK Platform Tools.

2. Run the following command, authorising your computer to access the device if you have not already:

adb backup -apk -obb -shared -all -system

3. Follow the instructions. In my case, I needed to unlock the device and confirm the backup operation (optionally entering a password to encrypt the backup).

This will store a file in the current working directory.

Restore

1. Ensure the device to restore to is connected.

2. Run:

Using .netrc with curl for Automatic Authorisation

The ~/.netrc file can store credentials. This can include things like OAuth tokens and plain text passwords.

Warning: Be very careful if you decide to store passwords in this file. The file is not encrypted, so you’ll be storing your password in plain text on the disk. This is generally a bad idea!

First, create the file and make it readable by only yourself:

touch ~/.netrc
chmod go= ~/.netrc

Then edit the file to contain lines that look like the following (one line per machine):

curl can then read this file by providing the --netrc option:

Ignore a Package Update When Using Fedora and KDE

Recently I wrote about Escaping a login loop when using Fedora. Well, once I had downgraded the package, I wanted to ensure that it would not get automatically updated again!

To ignore the package when performing updated via dnf, add an exclude=<package> line to /etc/dnf/dnf.conf. For example:

[main]
gpgcheck=1
installonly_limit=3
clean_requirements_on_remove=True
exclude=sddm

dnf no longer requests me to update SDDM.

Unfortunately, the built-in updater for KDE (which I blieve is PackageKit) does not honour the settings in dnf.conf. It will, however, honour exclude= lines in the repo files in /etc/yum.repos.d.

Since I wanted to block an update to SDDM, I edited /etc/yum.repos.d/fedora-updates.repo and added an exclude=sddm directive to the [updates] block:

name=Fedora $releasever -$basearch - Updates
failovermethod=priority
#baseurl=http://download.fedoraproject.org/pub/fedora/linux/updates/$releasever/$basearch/
metalink=https://mirrors.fedoraproject.org/metalink?repo=updates-released-f$releasever&arch=$basearch
enabled=1
repo_gpgcheck=0
type=rpm
gpgcheck=1
gpgkey=file:///etc/pki/rpm-gpg/RPM-GPG-KEY-fedora-$releasever-$basearch
skip_if_unavailable=False
exclude=sddm

After a while, KDE stopped pestering me to install the SDDM update.

I technically probably only have to add the exclude to the repo files, but this is the process that I went through. If you’re feeling adventurous, you may try only updating the repo files.

The problem seems to be caused by an update to SDDM (Simple Desktop Display Manager).

On Fedora it can be downgraded, but first you need an internet connection. I enabled my wireless internet connection by running:

nmcli connection up <wireless-network>

Where <wireless-network> is the SSID of my wireless network.

Logins should then work after a reboot.

When I tried to start partitionmanager (KDE Partition Manager) on Fedora 26, it would always ask for the root user’s password, despite the fact that the root user was disabled in my setup.

The dialog box that popped up looked like it might be kdesu. kdesu,. a.k.a. KDE su, is a KDE version of su that allows a process to be run as another user, like root. When I tried running kdesu separately it asked for root’s password again. So I knew the problem lay within kdesu, not partitionmanager.

The ever-helpful Arch wiki contained just the golden nugget I was after: a command that would configure kdesu to use sudo:

kwriteconfig5 --file kdesurc --group super-user-command --key super-user-command sudo

This fixed the problem for me, as sudo requests your password, not root’s. Whether you’re allowed to run the command depends on the contents of the system’s sudoers file. Look that file up if you continue to have difficulty.

Run Apache Directory Studio With Java 10

You can find this file:

• On Linux: in the installation folder
• On Mac OS X: /Applications/ApacheDirectoryStudio.app/Contents/ApacheDirectoryStudio.ini
• On Windows: in the installation folder

Re-use Commit Message in Git

To re-use a commit’s message verbatim, including authorship and timestamp information, use -C <commit>:

git commit --amend -C @

Pro Tip: @ is a synonym for HEAD, the currently checked-out commit.

To reset the date as well, use --date now; to reset the author too, use --reset-author:

git commit --amend -C @ --date now
git commit --amend -C @ --reset-author
git commit --amend -C @ --date now --reset-author

If you want to use an existing commit’s message and also want a chance to edit it, use -c <commit>:

git commit --amend -c @

-c is compatible with --date and --reset-author too:

git commit --amend -c @ --date now
git commit --amend -c @ --reset-author
git commit --amend -c @ --date now --reset-author


text:
Some new monotonicity theorems with applications to free boundary problems.(English)Zbl 1142.35382

This paper is devoted to some new monotonicity theorems with applications to free boundary problems. More precisely, the authors reformulate the theorem so that it applies to inhomogeneous equations in which the right-hand side of the equation need not vanish at the free boundary. Here particular interest is the case in which $$\Delta u$$ takes two different constant values on the set where $$u> 0$$ and on the set where $$u< 0$$. The new versions of the monotonicity theorem presented in the paper lead to existence of certain classical solutions to the Prandtl-Batchelor equation in two dimensions and partial regularity results in higher dimensions.

MSC:

 35J25 Boundary value problems for second-order elliptic equations 35B65 Smoothness and regularity of solutions to PDEs 35R35 Free boundary problems for PDEs
Full Text:


text:
#### Archived

This topic is now archived and is closed to further replies.

# Quaternions(again)

This topic is 5961 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

From looking at the forum I''m sure everyones sick of quaternions, but my question is simple: if quaternions are used to "represent a transformation" such as rotation in the form of 4 numbers w,x,y,z then how do I set these values for a transformation (or alter them) and then how do I use these values to do the transformations (I only need to end up with an angle and a vector for the opengl rotatef function.) I dont intend to understand how they actually work, at the moment, just to resolve my frustration about my failing 3d program. The "why"s and "how"s of it will be resolved some day, but can somone just answer these hopefully more straight forward questions. The help really will be appreciated, thanks.

##### Share on other sites
axis (X,Y,Z) angle (A) to quaternion (w,x,y,z) :

normalize (X,Y,Z) (X^2+Y^2+Z^2==1)
w = cos(A/2)
(x,y,z) = (X,Y,Z)*sin(A/2)

quaternion to axis/angle
A = 2*acos(w)
(X,Y,Z) = (x,y,z)/sqrt(1-w^2) // irrelevant if A == 0

quaternion to transformation matrix (will be faster than glRotate, use glMatrixMultiply). You might need to use the transposed of the following matrix though (element ordering...)
| 1-2yy-2zz   2xy+2wz   2xz-2wy 0 ||   2xy-2wz 1-2xx-2zz   2yz+2wx 0 ||   2xz+2wy   2yz-2wx 1-2xx-2yy 0 ||      0         0         0    1 |[code]Edited by - Fruny on February 25, 2002 5:41:13 PM

##### Share on other sites
Thank you so much. I''ve been looking for that answer for quite a while, that''s just I wanted. Thanx again.

1. 1
2. 2
3. 3
4. 4
Rutin
17
5. 5

• 11
• 20
• 12
• 11
• 41
• ### Forum Statistics

• Total Topics
631401
• Total Posts
2999869
×


text:
# Explicit formula of a fundamental matrix

I'm trying to solve the following differential system explicitly $$\left( \begin{array}{c} y \\ z% \end{array}% \right) ^{\prime }=\left( \begin{array}{cc} 0 & b(t) \\ \delta b(t) & a(t)% \end{array}% \right) \left( \begin{array}{c} y \\ z% \end{array}% \right) ,\text{ }\delta \in %TCIMACRO{\U{211d} }% %BeginExpansion \mathbb{R}$$ Can we find an explicit formula of the solutions? Thank you.

The matrix equation $$\frac{d\mathbf{x}}{dt} = A(t) \mathbf{x}$$ has solution
$$\displaystyle \mathbf{x}(t) = \mathbf{x}(0) e^{\int_0^t A(\tau) d\tau}.$$
$$\displaystyle \mathbf{x} = \begin{pmatrix} y\\z \end{pmatrix}, \quad e^{\int_0^\tau A d\tau} = I + \int_0^t d\tau \begin{pmatrix} 0 & b(t) \\ \delta b(t) & a(t) \end{pmatrix} + \frac{1}{2!} \left\{ \int_0^t d\tau \begin{pmatrix} 0 & b(t) \\ \delta b(t) & a(t) \end{pmatrix} \right\}^2 + \cdots$$
You can compute the elements of $$\mathbf{x}(t)$$ by summing the series.


text:
## Saturday, January 23, 2010

### Wmii: Dealing with a lack of xrandr support

I use wmii on my EeePC, which is frequently connected to and disconnected from an external monitor. Earlier I posted about how to get my DPI under control using two monitors, but a different issue I had was with wmii and the lack of xrandr support. When I plug in the external monitor, I get a lot of extra screen real estate, but the status bar stays in the same place instead of moving to the bottom of the screen to take advantage of that extra real estate.

The unhappy workaround to this problem is to place this in your .xsession:

while true; do
wmii
done

If you do this and login via gdm by selecting "XClient script" as your session, you can quit wmii without stopping X. This will re-launch wmii and all your windows will be retagged. Not optimal, but it will do for now.


text:
# The Fundamental Theorem of Arithmetic

This post discusses and proves the fundamental theorem of arithmetic.

Finding the prime factors of a large integer is no easy feat. For example, the ninth Fermat number $F_9=2^{2^9}+1$ has 155 digits and has the following three prime factors:

$a=\text{2,424,833}$

$b=\text{7,455,602,825,647,884,208,337,395,736,200,454,918,783,366,342,657}$

\displaystyle \begin{aligned} c=&\text{ 741,640,062,627,530,801,524,787,141,901,937,474,059,940,781,097,519} \\&\text{ 023,905,821,316,144,415,759,504,705,008,092,818,711,693,940,737} \end{aligned}

These prime factors have 9 digits, 49 digits and 99 digits, respectively. They were published in 1993 after lengthy calculations involving approximately 700 workstations and a supercomputer using a number field sieve algorithm (see [1]). If the project were to be done today, it could certainly be done much faster and more efficiently with the current state of the art in supercomputing. However, the project will still be no trivial feat.

The following 617-digit integer is a product of two prime numbers and has yet to be factored by anyone (or any computer or any sets of computers). According RSA Laboratories, barring fundamental algorithmic or computing advances, the above number or other similarly sized number is expected to stay unfactored in the decades to come. For more background about this large number, see see RSA challenge number and RSA factoring challenge.

25195908475657893494027183240048398571429282126204
03202777713783604366202070759555626401852588078440
69182906412495150821892985591491761845028084891200
72844992687392807287776735971418347270261896375014
97182469116507761337985909570009733045974880842840
17974291006424586918171951187461215151726546322822
16869987549182422433637259085141865462043576798423
38718477444792073993423658482382428119816381501067
48104516603773060562016196762561338441436038339044
14952634432190114657544454178424020924616515723350
77870774981712577246796292638635637328991215483143
81678998850404453640235273819513786365643912120103
97122822120720357

Though the implementation of prime factorization may be difficult or even impossible for large numbers, the fundamental theorem of arithmetic guarantees that any positive integer can be expressed uniquely as a product of prime numbers. The fundamental theorem of arithmetic is an essential theorem in number theory. In this post, we present of proof of this fundamental theorem.

___________________________________________________________________________________________________________________

The Fundamental Theorem of Arithmetic

The theorem has two parts – the existence and the uniqueness of the prime factorization. The existence part is relatively easy. We first prove the existence part. We use Euclid’s lemma to prove the uniqueness part.

Lemma 1

Any integer $n>1$ has a prime divisor.

Proof

Let $n$ be an integer with $n>1$. If $n$ is prime, then it has a prime divisor, namely $n$. So assume $n$ is not prime. Then $n=h \cdot k$ for some positive integers $h$ and $k$ smaller than $n$.

Now consider the set $D$ of all positive integer divisors of $n$. The set $D$ is nonempty since $h$ and $k$ belong to this set. The set $D$ is also a finite set since an integer can only have finitely many integer divisors. Every finite set of real numbers has a smallest element. Let $p$ be the least element of $D$.

The $p$ must be a prime number. If not, $p$ would have a positive divisor $q$ that is smaller than $p$. Then $q$ is also a positive divisor of $n$, contradicting that $p$ is the least element of $D$. $\blacksquare$

Lemma 2

Any integer $n>1$ is a product of prime numbers.

Proof

We prove by induction. The lemma is certainly true for $n=2$. Suppose the lemma is true for all positive integers $k$ where $k.

If $n$ is prime, then we are done. Assume $n$ is not prime. Then $n=h \cdot k$ for some positive integers $h$ and $k$ smaller than $n$. By induction hypothesis, both $h$ and $k$ are product of prime numbers. We can conclude that $n$ is also a product of prime numbers. $\blacksquare$

Euclid’s Lemma

If $p$ is a prime number and $p \ \lvert (a \cdot b)$, then $p \ \lvert \ a$ or $p \ \lvert \ b$.

Proof of Euclid’s Lemma is found in this post. As a corollary of Euclid’s Lemma, we have the following lemma.

Lemma 3

If $p$ is a prime number and $p \ \lvert (a_1 \cdot a_2 \cdots a_n)$, then $p \ \lvert \ a_i$ for some $i$.

Proof

We prove by induction. The case for $n=2$ is the Euclid’s Lemma. Assume that the lemma is true for $n$ where $n \ge 2$. Suppose that $p \ \lvert (a_1 \cdot a_2 \cdots a_n \cdot a_{n+1})$. By Euclid’s lemma, we have $p \ \lvert (a_1 \cdot a_2 \cdots a_n)$ or $p \ \lvert \ a_{n+1}$. In the first case, the induction hypothesis tells us that $p \ \lvert \ a_i$ for some $i$ with $1 \le i \le n$. In the second case $p \ \lvert \ a_{n+1}$. The two cases together tell us that $p \ \lvert \ a_i$ for some $i$ with $1 \le i \le n+1$.

Since the validity of the lemma for $n$ implies the validity of the lemma for $n+1$ and since the lemma is true for $n=2$, we now know that the lemma is true for all integers $n>1$. This establishes the lemma. $\blacksquare$

Fundamental Theorem of Arithmetic

Any interger $n>1$ can be expressed uniquely as a product of prime numbers.

Proof

Let $n$ be an integer with $n>1$. The existence of the prime factors of $n$ is established by Lemma 2. We now show there is only one prime factorization for $n$. We would like to point out that order of the prime factors is not important. For example, we consider $2 \times 2 \times 3 \times 11$ and $11 \times 3 \times 2 \times 2$ as the same factorization for the integer $132$.

Suppose that $n=p_1 \cdot p_2 \cdots p_h$ and $n=q_1 \cdot q_2 \cdots q_k$ are prime factorizations of the integer $n$. We show that each $p_i$ is identical to some $q_j$ and each $q_s$ is identical to some $p_t$. This implies that the prime numbers $p_1,p_2,\cdots,p_h$ are simply a rearrangement of $q_1,q_2,\cdots,q_k$ such that the only difference for the two factorizations is in the order of the factors.

Note that $p_1 \cdot (p_2 \cdots p_h)=q_1 \cdot q_2 \cdots q_k$. Thus $p_1$ divides $q_1 \cdot q_2 \cdots q_k$, or we write $p_1 \ \lvert \ q_1 \cdot q_2 \cdots q_k$. By Lemma 3, $p_1 \ \lvert \ q_j$ for some $j$. Since they are prime, $p_1=q_j$. Then cancel out $p_1$ on both side of the equation, we have

$p_2 \cdot (p_3 \cdots p_h)=q_1 \cdot q_2 \cdots q_{j-1} \cdot q_{j+1} \cdots q_k$

Note that $p_2$ divides the right-hand side of the above equation. By Lemma 3, $p_2 \ \lvert \ q_w$ for some $w$. Continue in this same manner, we see that each $p$ is identical to some $q$. Furthermore, $h \le k$. Otherwise, there would be some $p_i$ left after we cancel out all the $q_j$, leading to the situation that the product of several prime numbers is equal to one.

By interchanging $p$ with $q$, the same argument will also show that each $q$ is identical to some $p$. Furthermore, $k \le h$. Thus we have $h=k$ and that the two factorizations are really just rearrangement of each other. $\blacksquare$

Comment

From the fundamental theorem of arithmetic, it follows that any positive integer greater than one can be expressed uniquely in the following way:

$p_1^{e_1} \cdot p_2^{e_2} \cdot p_3^{e_3} \cdots p_m^{e_m}$

where $m$ is a positive integer and each $e_i \ge 1$. Such representation of an integer is called a prime-power decomposition. For example, $7056=2^4 \cdot 3^2 \cdot 7^2$.

___________________________________________________________________________________________________________________

Reference

1. Lenstra, A. K., Lenstra, H. W., Manasse, M. S., Pollard, J. M. The Factorization of the Ninth Fermat Number, Mathematiics of Computation, Volume 61, Number 203, July 1993, Pages 319-349.

___________________________________________________________________________________________________________________

$\copyright \ 2013 \text{ by Dan Ma}$

# Euclid’s Lemma

This post presents a proof of a lemma that is called Euclid’s lemma, which is one of the fundamental properties of prime numbers. Euclid’s lemma is the statement that if a prime number divides a product of two integers, it must divide one of the factors.

This post is also part of the series of posts leading up to the fundamental theorem of arithmetic.

We first state all the tools that we need. The notation $a \ \lvert \ b$ refers to the condition that $a$ divides $b$. The notation $\text{GCD}(a,b)$ refers to the greatest common divisor (GCD) of $a$ and $b$.

___________________________________________________________________________________________________________________

Extended Euclidean Algorithm

Let $a$ and $b$ be integers. Let $d$ be the greatest common divisor of $a$ and $b$. Then there exist integers $x$ and $y$ such that $ax+by=d$.

The extended Euclidean algorithm is discussed in this post.

___________________________________________________________________________________________________________________

Lemma 1

If $d \ \lvert \ a \cdot b$ and $\text{GCD}(d,a)=1$, then $d \ \lvert \ b$.

Proof of Lemma 1

Suppose that $d \ \lvert \ a \cdot b$ and $\text{GCD}(d,a)=1$. According to the extended Euclidean algorithm, for some integers $x$ and $y$, we have $ax+dy=1$. Multiplying both sides by $b$, we have:

$abx+dby=b$

Since $d$ divides each term in the left-hand side of this equation, $d \ \lvert \ b$. $\blacksquare$

___________________________________________________________________________________________________________________

Euclid’s Lemma

If $p$ is a prime number and $p \ \lvert (a \cdot b)$, then $p \ \lvert \ a$ or $p \ \lvert \ b$.

Proof

If $p \ \lvert \ a$, then we are done. So assume $p \not \lvert \ a$, which implies that $\text{GCD}(p,a)=1$. If $\text{GCD}(p,a)>1$, $\text{GCD}(p,a)=p$, which implies that $p \ \lvert \ a$. Note that the only positive divisors of $p$ are $1$ and $p$. By Lemma 1, $p \ \lvert \ b$. $\blacksquare$

Comment

We would like to point out that the assumption that $p$ is prime is essential in Euclid’s lemma. Note that $8 \ \lvert \ (4 \cdot 4)$ and $8 \not \lvert \ 4$.

___________________________________________________________________________________________________________________

$\copyright \ 2013 \text{ by Dan Ma}$

# The Euclidean Algorithm

In this post, we discuss the Euclidean algorithm, which is an algorithm to find the greatest comment divisor of two integers. This post is also part of the series of posts leading up to the fundamental theorem of arithmetic.

___________________________________________________________________________________________________________________

Introduction

Computing the greatest common divisor of two integers is a topic that is taught in elementary school and is also an important tool that is of great interest in number theory. We begin with an example.

Let’s take a simple example of finding the greatest common divisor of 24 and 60. In a math class in elementary school, one motivation of finding the greatest common divisor of 24 and 60 is to reduce the fraction $\displaystyle \frac{24}{60}$ to its lowest terms. The first step is to factor each of the numerator and denominator using their prime factors.

$\displaystyle \frac{24}{60}=\frac{2 \cdot 2 \cdot 2 \cdot 3}{2 \cdot 2 \cdot 3 \cdot 5}$

Then cross out the prime factors common to the numerator and the denominator.

$\displaystyle \frac{24}{60}=\frac{\not 2 \cdot \not 2 \cdot 2 \cdot \not 3}{\not 2 \cdot \not 2 \cdot \not 3 \cdot 5}=\frac{2}{5}$

The product of the prime factors that are crossed out is $2 \cdot 2 \cdot 3=12$, which is the greatest common divisor of 24 and 60.

Thus the greatest common divisor of two integers $a$ and $b$ is the product of the prime factors shared by the two numbers. This approach of finding the greatest common divisor depends on performing prime factorization, which is a hard problem for larger numbers. This approach, though conceptually clear, is clearly not efficient.

We need an algorithm for finding the greatest common divisor that does not require prime factorization. First, we have another discussion on the greatest common divisor.

___________________________________________________________________________________________________________________

The Greatest Common Divisor

Let $a$ and $b$ be integers. We say that $a$ divides $b$ (denoted by $a \ \lvert \ b$) if there is an integer $q$ such that $b=q \cdot a$. In other words, $a \ \lvert \ b$ if $a$ divides $b$ without leaving a remainder. For examples, $3 \ \lvert \ 18$ and $7 \ \lvert \ 91$. When $a$ does not divide $b$, we write $a \not \lvert \ b$.

The greatest common divisor (or GCD) of two integers $a$ and $b$ is denoted by $\text{GCD}(a,b)$ and is the largest positive integer that divides both $a$ and $b$. It is clear that $\text{GCD}(a,b)$ is the positive integer $d$ such that

• $d \lvert a$ and $d \lvert b$.
• If $c \lvert a$ and $c \lvert b$, then $c \le d$.

The greatest common integer $\text{GCD}(a,b)$ is always uniquely defined. Each integer has only finitely many integer divisors. So there are only finitely many divisors common to both $a$ and $b$ (the integer 1 is one of them). Any finite set of real numbers has a unique largest element. Thus among all the common divisors of $a$ and $b$, there is the largest one, which we denote by $\text{GCD}(a,b)$. Consequently, $\text{GCD}(a,b) \ge 1$.

We can observe that the greatest common integer $\text{GCD}(a,b)$ defined in this section is identical to the product of the prime factors shared by the two integers $a$ and $b$.

To perform the Euclidean algorithm, we need the division algorithm and the following lemma.

Division Algorithm
Let $a$ and $b$ be positive integers. Then there exist unique integers $q$ and $r$ such that

$a = q \cdot b + r$

where $0 \le r .

Lemma 1
Let $a$ and $b$ be positive integers. If $a=q \cdot b+r$, then $\text{GCD}(a,b)=\text{GCD}(b,r)$.

For the discussion in this post, Lemma 1 is used in conjunction with the division algorithm. So we put Lemma 1 in words in the context of applying the division algorithm as follows.

Lemma 1. When $a$ is divided by $b$, the GCD of $a$ and $b$ is the same as the GCD of the $b$ (the divisor) and the $r$ (the remainder).

Proof of Lemma 1

Suppose that $a=q \cdot b+r$. Let $h=\text{GCD}(a,b)$ and $k=\text{GCD}(b,r)$.

We first show that $h \le k$. Since $a=q \cdot b+r$ and since $h \ \lvert \ a$ and $h \ \lvert \ b$, we have $h \ \lvert \ r$. Since $h$ is a common divisor of $b$ and $r$, $h \le k$.

Now we show $k \le h$. Since $a=q \cdot b+r$, it follows that $k$ is a common divisor of $a$ and $b$. Thus $k \le h$. $\blacksquare$

___________________________________________________________________________________________________________________

Example for the Euclidean Algorithm

Before defining the Euclidean algorithm, let’s look at an example. Find the greatest common divisor of $1638$ and $357$.

The Euclidean algorithm can be implemented using subtraction or division.

In the subtraction implementation, the Euclidean algorithm starts with a pair of positive integers and forms a new pair that consists of the smaller integer and the difference between the larger and smaller integers. The process repeats until the two integers are equal. That number then is the greatest common divisor of the original pair.

The following series of subtractions derives the GCD of $1638$ and $357$.

$\displaystyle (1) \ \ \ \ \ \ \ \ \begin{bmatrix} \text{ }&\text{ }&\text{Number 1}&\text{ }&\text{Number 2} \\\text{ }&\text{ }&\text{ } \\ 1&\text{ }&1638&\text{ }&357 \\ 2&\text{ }&1281&\text{ }&357 \\ 3&\text{ }&924&\text{ }&357 \\ 4&\text{ }&567&\text{ }&357 \\ 5&\text{ }&210&\text{ }&357 \\ 6&\text{ }&210&\text{ }&147 \\ 7&\text{ }&63&\text{ }&147 \\ 8&\text{ }&63&\text{ }&84 \\ 9&\text{ }&63&\text{ }&21 \\ 10&\text{ }&42&\text{ }&21 \\ 11&\text{ }&21&\text{ }&21 \end{bmatrix}$

In the above table, to go from one row to the next, the larger number is reduced by the smaller number. The process stops when the two numbers are equal. In this example, the greatest common divisor is $21$.

Note that the above subtraction process can be speeded up by doing division instead. For example, in the above table, you can jump from row 1 to row 5 by applying the division algorithm. The following is the same example using the division implementation.

$\displaystyle (2) \ \ \ \ \ \ \ \ \begin{bmatrix} \text{ }&\text{ }&\text{Number 1}&\text{ }&\text{Number 2} \\\text{ }&\text{ }&\text{ } \\ 1&\text{ }&1638&\text{ }&357 \\ 2&\text{ }&210&\text{ }&357 \\ 3&\text{ }&210&\text{ }&147 \\ 4&\text{ }&63&\text{ }&147 \\ 5&\text{ }&63&\text{ }&21 \\ 6&\text{ }&0&\text{ }&21 \end{bmatrix}$

To go from row 1 to row 2, divide $1638$ by $357$ to obtain the remainder $210$. To go from row 2 to row 3, divide the larger number $357$ by $210$ to obtain the remainder $147$. Repeat the process until one of reaching the remainder of zero. Then the other number in the last row is the greatest common divisor. The following is the same algorithm with the divisions added.

$\displaystyle (3) \ \ \ \ \ \ \ \ \begin{bmatrix} \text{ }&\text{ }&\text{Number 1}&\text{ }&\text{Number 2}&\text{ }&\text{Division} \\\text{ }&\text{ }&\text{ } \\ 1&\text{ }&1638&\text{ }&357&\text{ }&1638=4 \cdot 357+210 \\ 2&\text{ }&210&\text{ }&357&\text{ }&357=1 \cdot 210+147 \\ 3&\text{ }&210&\text{ }&147&\text{ }&210=1 \cdot 147+63 \\ 4&\text{ }&63&\text{ }&147&\text{ }&147=2 \cdot 63+21 \\ 5&\text{ }&63&\text{ }&21&\text{ }&63=3 \cdot 21+0 \\ 6&\text{ }&0&\text{ }&21 \end{bmatrix}$

As shown in the example, the Euclidean algorithm only requires subtractions or divisions and no prime factorization. Note that Lemma 1 is used throughout the two tables. Let’s look at table (3). Because the GCD of two numbers is the same as the divisor and the remainder (Lemma 1), the GCD of any row is identical to the GCD of the row below.

___________________________________________________________________________________________________________________

The Euclidean Algorithm

In the remainder of the post, we only discuss the division implementation of the Euclidean algorithm. The following is the description of the Euclidean algorithm.

Euclidean Algorithm

Let $a_0$ and $b_0$ be positive integers. Assume $b_0. Start with the pair $(a_0,b_0)$ and forms a new pair that consists of the smaller number and the remainder derived from dividing the larger number by the smaller. The process stops when reaching a remainder of zero. Then the other number in the last pair is the GCD of $a_0$ and $b_0$.

To describe using some notations, we have the following divisions.

$a_0=q_0 \cdot b_0+r_0 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 0 \le r_0

$b_0=q_1 \cdot r_0+r_1 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 0 \le r_1

$r_0=q_0 \cdot r_1+r_2 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 0 \le r_2

$\cdots \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \cdots$

$\cdots \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \cdots$

$\cdots \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \cdots$

$r_k=q_k \cdot r_{k+1}+r_{k+2} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 0 \le r_{k+2}

The above series of divisions will stop at some $k=j$ where the remainder $r_{j+2}=0$. We have $r_j=q_j \cdot r_{j+1}$ where $r_{j+1}$ is the GCD of the original pair $(a_0,b_0)$.

Proof of Euclidean Algorithm
In the above notation, the sequence of non-negative numbers $b_0>r_0>r_1>r_2>\cdots$ must stop at some point. Eventually $r_{j+2}=0$ for some $j$. We have $r_j=q_j \cdot r_{j+1}+0$. Then $\text{GCD}(r_j,r_{j+1})=\text{GCD}(r_{j+1},0)=r_{j+1}$.

Applying Lemma 1 repeatedly, we have:

\displaystyle \begin{aligned} r_{j+1}&=\text{GCD}(r_{j+1},0) \\&=\text{GCD}(r_j,r_{j+1}) \\&\cdots \\&\cdots \\&\cdots \\&=\text{GCD}(r_1,r_{2}) \\&=\text{GCD}(r_0,r_{1}) \\&=\text{GCD}(b_0,r_{0}) \\&=\text{GCD}(a_0,b_{0}) \end{aligned}

Comment. Note that the statement of the Euclidean algorithm starts with a pair of positive integers $(a_0,b_0)$. If either number is negative, we can take the absolute value of the numbers and the resulting GCD is the same as the original pair. This follows from the following fact.

$\text{GCD}(a,b)=\text{GCD}(-a,b)=\text{GCD}(a,-b)=\text{GCD}(-a,-b)$

___________________________________________________________________________________________________________________

The Extended Euclidean Algorithm

Another good use of the Euclidean algorithm is to find integer solutions to the linear equation $ax+by=d$ where $d=\text{GCD}(a,b)$. This is called the extended Euclidean algorithm. We state it in the following lemma.

Lemma 2 (The Extended Euclidean Algorithm)
Let $a$ and $b$ be integers. Let $d=\text{GCD}(a,b)$. Then there are integers $x$ and $y$ that satisfies the equation $ax+by=d$.

Proving Lemma 2 is a matter of working the Euclidean algorithm backward. We demonstrate the idea using our example of $a=1638$ and $b=357$. The following shows the divisions used in Table (3) above.

$1638=4 \cdot 357+210$
$357=1 \cdot 210+147$
$210=1 \cdot 147+63$
$147=2 \cdot 63+21$
$63=3 \cdot 21+0$

We start off with the second to the last division and work backward.

\displaystyle \begin{aligned} 21&=147-2 \cdot 63 \\&=147 - 2 \cdot (210-147) \\&=3 \cdot 147-2 \cdot 210 \\&=3 \cdot (357-210)-2 \cdot 210 \\&=3 \cdot 357 -5 \cdot 210 \\&=3 \cdot 357- 5 \cdot (1638- 4 \cdot 357) \\&=(-5) \cdot 1638+23 \cdot 357 \end{aligned}

The equation $1638x+357y=21$ has solution $x=-5$ and $y=23$.

As an application to the extended Euclidean algorithm, we have the following corollary.

Corollary 3
Let $a$ and $b$ be integers. Let $h=\text{GCD}(a,b)$. Then if $k$ is a common divisor of $a$ and $b$, then $k$ is a divisor of $h$.

Proof of Corollary
According to Lemma 2, there are integers $x$ and $y$ such that $ax+by=h$. Note that $k$ divides each term on the left-hand side of this equation. So $k$ divides $h$ as well. $\blacksquare$
___________________________________________________________________________________________________________________

$\copyright \ 2013 \text{ by Dan Ma}$

# The Division Algorithm

The division algorithm is the conceptual underpinning of many concepts in number theory (congruence arithmetic is one example). In this post, we present a proof of the division algorithm and connect it to one important property of congruence.

This post is also part of the series of posts leading up to the fundamental theorem of arithmetic.

___________________________________________________________________________________________________________________

The Division Algorithm

The following is the statement of the division algorithm.

Let $a$ and $b$ be positive integers. Then there exist unique integers $q$ and $r$ such that

$a = q \cdot b + r$

where $0 \le r .

Let $A$ be the set $A=\left\{a-jb: j=0,1,2,3,\cdots \right\}$. Let $A_+$ be the following subset of $A$.

$A_+=\left\{x \in A: x \ge 0 \right\}$

The set $A_+$ is a set of non-negative integers. Hence it must have a least element, say $r$. Then we have $r=a-qb$ for some positive integer $q$. Furthermore, we have $0 \le r. If $r>b$, $r$ would not be the least element of $A_+$ since we can subtract $b$ into $r$ to obtain $a-(q+1)b$, which is less than $r$ and is an element of $A_+$.

We now have found integers $q$ and $r$ such that $a = q \cdot b + r$. It remains to show that the integers $q$ and $r$ are unique. Suppose there are also integers $q_0$ and $r_0$ such that

$a=q \cdot b + r=q_0 \cdot b + r_0$

After subtracting, $(q-q_0) \cdot b + (r-r_0)=0$. Since $b$ divides both $0$ and $(q-q_0) \cdot b$, $b$ must divides $r-r_0$. This means that $r-r_0=0$, since both $r$ and $r_0$ are non-negative integers that are less than $b$. Thus $r=r_0$ and in turns $q-q_0$. $\blacksquare$

Conceptually the division algorithm tells us that there is a unique remainder $r$ upon division of $a$ by $b$. In terms of actual computation, it does not tell us how to find the remainder or the quotient. However it is the conceptual underpinning of many concepts and ideas in number theory.

___________________________________________________________________________________________________________________

Congruence

We now use the division algorithm to prove one important property of congruence. The symbol $a \equiv b \ (\text{mod} \ m)$ means that $m$ divides $a-b$ (in words, we say $a$ is congruent to $b$ modulo $m$). For a basic discussion of congruence arithmetic, see “A basic discussion of congruences”. We prove the following property of congruence.

For every integer $a$, $a \equiv r \ (\text{mod} \ m)$ for a unique integer $r$ with $0 \le r.

In other words, any integer is congruence modulo $m$ to one and only one element $r$ in the set $\left\{0,1,2,\cdots,m-1 \right\}$. The integer $r$ is called the least residue of $a$ modulo $m$.

The above property about least residue follows from the division algorithm. Let $a$ be any integer. If $a=0$, clearly $a \equiv 0 \ (\text{mod} \ m)$. We can assume that $a \ne 0$.

Now consider the case that $a>0$. By the division algorithm, there are integers $q$ and $r$ such that $a=q \cdot m+r$ where $0 \le r . Thus $a \equiv r \ (\text{mod} \ m)$.

Consider the case that $a<0$. By the division algorithm, there are integers $q$ and $r$ such that $-a=q \cdot m+r$ where $0 \le r . Immediately we have $a=(-q) \cdot m+(-r)$. Thus $a \equiv -r \ (\text{mod} \ m)$. Note that $-r \equiv m-r \ (\text{mod} \ m)$. Thus $a \equiv m-r \ (\text{mod} \ m)$/

One concluding remark is that any least residue that is found in the above argument is unique. This is because no two distinct elements of the set $\left\{0,1,2,\cdots,m-1 \right\}$ can be congruent to each other. $\blacksquare$

___________________________________________________________________________________________________________________

$\copyright \ 2013 \text{ by Dan Ma}$

# A basic discussion of congruences

When performing the division $45 \div 7$, the remainder is $3$. What is the remainder in the division $9664^{79081} \div 55049$? What is the remainder in the division of $(2^{57885161} - 1)$ by $524287$? If you have special software, you can determine quickly that the remainder for the first question is the number $1020$. Note that the number $2^{57885161} - 1$ in the second question is the current largest known prime number at the writing of this post. The special software you use might have to struggle a little to come up with the answer of $255$. Without special software, you can use congruence arithmetic to perform the above calculations.

Congruence notation was invented by the great mathematician Carl Friedrich Gauss (1777 – 1855). It is hard to overstate the importance of the role of congruence in number theory. The notion not only eases calculation but also makes statements of theorems much easier to state and simplifies the proofs of theorems. This post is a basic discussion of congruence.

For more information about congruence or modular arithmetic, see the number theory introductory text [1] or the Wikepedia entry on modular arithmetic.

___________________________________________________________________________________________________________________

Basic Discussion

Given integers $a$, $b$ and $m$ with $m>0$, the statement that $a$ is congruent to $b$ modulo $m$ means that the difference $a-b$ is divisible by $m$. In symbol, we write $a \equiv b \ (\text{mod} \ m)$. The number $m$ is the modulus of the congruence. We also use the notation $m \lvert a-b$ to refers to the statement that $a-b$ is divisible by $m$. We repeat the definition below.

$a \equiv b \ (\text{mod} \ m) \ \ \ \Longleftrightarrow \ \ \ m \lvert a-b \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)$

The following two properties of congruence that can be easily verified from definition $(1)$.

$a \equiv b \ (\text{mod} \ m) \ \ \ \Longleftrightarrow \ \ \ a=b+k \cdot m \text{ for some integer } k \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (2a)$

$b+k \cdot m \equiv b \ (\text{mod} \ m) \text{ for all integers } k \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (2b)$

Another meaning of congruence modulo $m$ comes from the division algorithm. For example, the division $45 \div 7$ gives the remainder $3$, i.e., $45=6 \cdot 7 +3$. So for the division $a \div m$ where both $a$ and $m$ are both positive, we have $a=q \cdot m+r$ for some integer $r$ with $0 \le r (call the remainder) and some integer $q$. From this we can conclude that every integer $a$ is congruent modulo $m$ to exactly one integer from the set $\left\{0,1,2,\cdots,m-1 \right\}$. The integer $r$ is called the least residue of $a$ modulo $m$. We summarize as follows: for every integer $a$,

$a \equiv r \ (\text{mod} \ m) \text{ for a unique integer } r \text{ with } 0 \le r < m \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (3)$

For a proof of property (3), see this post. Another characteristic of congruence modulo $m$ is the following property.

$a \equiv b \ (\text{mod} \ m) \Longleftrightarrow \text{ each of } a \text{ and } b \text{ leaves the same remainder }$

$\text{ when divided by } m \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (4)$

All the above conditions point to the cyclical nature of congruence, which can be visualized in a diagram. The figure is below describes congruence modulo $12$.

You can start at any point in the above diagram. Every time you add or subtract the modulus $m=12$, you go around the circle and come back to the same point you start from (conditions 2 and 4). Two integers are related congruence modulo $12$ if they can be reduced by the division algorithm to the same time in the clock (condition 3).

___________________________________________________________________________________________________________________

Some Properties for Congruence

Congruence arithmetic is similar to conventional arithmetic. However, there are important differences. For example, comparing congruence with the equality sign = will help us see some of the differences. To set up the comparison, the following are some operations on real numbers we would like to focus on:

Operations on real numbers:

$a=b \ \ \Longrightarrow \ \ b=a \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{R1}$

$a=b \text{ and } b=c \ \ \Longrightarrow \ \ a=c \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{R2}$

$a=b \text{ and } c=d \ \ \Longrightarrow \ \ a+c=b+d \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{R3}$

$a=b \text{ and } c=d \ \ \Longrightarrow \ \ a \cdot c=b \cdot d \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{R4}$

$ac=bc \text{ and } c \ne 0 \ \ \Longrightarrow \ \ a=b \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{R5}$

All the above arithmetic operations on real numbers have analog in congruence except for R5. The following are the equivalence in congruence operations.

$a \equiv b \ (\text{mod} \ m) \ \ \Longrightarrow \ \ b \equiv a \ (\text{mod} \ m) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{C1}$

$a \equiv b \ (\text{mod} \ m) \text{ and } b \equiv c \ (\text{mod} \ m) \ \ \Longrightarrow \ \ a \equiv c \ (\text{mod} \ m) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{C2}$

$a \equiv b \ (\text{mod} \ m) \text{ and } c \equiv d \ (\text{mod} \ m) \ \ \Longrightarrow \ \ a+c \equiv b+d \ (\text{mod} \ m) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{C3}$

$a \equiv b \ (\text{mod} \ m) \text{ and } c \equiv d \ (\text{mod} \ m) \ \ \Longrightarrow \ \ a \cdot c \equiv b \cdot d \ (\text{mod} \ m) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{C4}$

$a \cdot c \equiv b \cdot c \ (\text{mod} \ m) \text{ and } c \not \equiv 0 \ (\text{mod} \ m) \ \ \Longrightarrow \ \ a \equiv b \ (\text{mod} \ m) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{C5}$

C5 has the additional requirement that $c$ and the modulus $m$ are coprime.

The properties C3 and C4 indicate that congruences may be validly added, subtracted and multiplied.

Note that the direct analog of R5 is not true in general. For example, $20 \equiv 2 \ (\text{mod} \ 6)$. However, $10 \not \equiv 1 (\text{mod} \ 6)$. In this case we cannot cancel out the common factor of $2$ on both sides of the congruence. When the additional requirement that the common factor $c$ and the modulus $m$ are coprime (i.e. the greatest common divisor is $1$), we can cancel out the common factor (as indicated by C5).

The derivation of the properties C1 through C4 is straightforward. The proof of C5 relies on Euclid’s lemma.

___________________________________________________________________________________________________________________

Some Examples

The properties in the above section are not meant to be memorized. The best approach is to work examples.

One typical congruence calculation is to find the least residue of a number $a$ modulo $m$. The number $a$ could be a sum or a product. Or it could be some number raised to an exponent. For the case of sum or product, we can start by reducing the components in the sum or product. For the case of an exponential, we can sometimes break it up into product of smaller numbers or use a “divide and conquer” approach. Let’s look at some examples.

To find $55 \cdot 67$ congruence modulo $7$, we do not need to first multiply. We can start by reducing each of the factors as follows:

$55 \cdot 67 \equiv 6 \cdot 4 \equiv 24 \equiv 3 \ (\text{mod} \ 7)$

In the above calculation we use property C4. We have $55 \equiv 6 \ (\text{mod} \ 7)$ and $67 \equiv 4 \ (\text{mod} \ 7)$. Thus $55 \cdot 67 \equiv 6 \cdot 4 \ (\text{mod} \ 7)$. We really do not need to be too conscious of which property to use. Just work enough examples and the process will flow quite naturally.

To find $1567 \equiv (\text{mod} \ 13)$, we can start by breaking up the number $1567$. The following is one example of how to do so.

\displaystyle \begin{aligned} 1567&=30 \cdot 50 + 67 \\&=31 \cdot 50 + 17 \\&\equiv 5 \cdot 11+4=59 \ (\text{mod} \ 13)\\&=50+9 \\&\equiv 11+9 \ (\text{mod} \ 13)=20 \\&\equiv 7 \ (\text{mod} \ 13) \end{aligned}

In the above calculation, we break up $1567$ into multiple of $50$ with $17$ added. Then starting reducing each of the numbers. Then multiply and sum to get $59$. We then break it up into $50$ and $9$, which is reduced into $11$ and $9$. Finally $20$ is reduced into $7$ modulo $13$. The properties used are C3 and C4. Once again, this type of calculation will flow naturally after working a few examples.

To find $55^{23} \equiv (\text{mod} \ 7)$, we can start by reducing the base $55$.

\displaystyle \begin{aligned} 55^{23}&\equiv 6^{23} \ (\text{mod} \ 7) \\&=(6^2)^{11} \cdot 6 \\&\equiv (1)^{11} \cdot 6 \ (\text{mod} \ 7) \\&\equiv 6 \ (\text{mod} \ 7) \end{aligned}

It follows from property C4 that if $a \equiv b \ (\text{mod} \ m)$, then $a^n \equiv b^n \ (\text{mod} \ m)$. Based on this idea, we can reduce base $55$ to the smaller base of $6$. We then reduce the exponent $23$ to the exponent of $11$. Such a process is a “divide and conquer” process that repeatedly reduces the exponent by half down to a manageable size.

Another example. Find the $2^{100} \equiv (\text{mod} \ 101)$. Note that $2^7=128$ and $128 \equiv 27 \ (\text{mod} \ 101)$.

\displaystyle \begin{aligned} 2^{100}&= (2^{7})^{14} \cdot 2^2 \\&\equiv (27)^{14} \cdot 4 \ (\text{mod} \ 101) \\&= (27^2)^{7} \cdot 4 \\&\equiv 22^7 \cdot 4 \ (\text{mod} \ 101) \\&=(22^2)^3 \cdot 22 \cdot 4 \\&\equiv 80^3 \cdot 88 \ (\text{mod} \ 101) \\&=80^2 \cdot 80 \cdot 88 \\&\equiv 37 \cdot 80 \cdot 88 \ (\text{mod} \ 101) \\&=2960 \cdot 88 \\&\equiv 31 \cdot 88 \ (\text{mod} \ 101) \\&\equiv 1 \ (\text{mod} \ 101) \end{aligned}

The key to a reduction of power in a congruence calculation is to find the right starting point. In the above example, exponent is reduced from $100$ to $14$, Then subsequently, keep reducing the exponent by half in each step until reaching a size that is manageable or easy to do.

It also follows from Fermat’s little theorem that $2^{100} \equiv 1 \ (\text{mod} \ 101)$.

___________________________________________________________________________________________________________________

More Examples

It is well known, even to some elementary school children, that an integer is divisible by nine if the sum of the digits is divisible by nine. The proof of this fact is very easy if done using congruence. The idea for the proof will be clear from the following example.

The number $55953$ is divisible by nine since $55953 = 9 \cdot 6217$. Also note that the sum of its digits is $27$. We can also look at the congruence angle. First, $10 \equiv 1 \ (\text{mod} \ 9)$, $10^2 \equiv 1 \ (\text{mod} \ 9)$ and $10^3 \equiv 1 \ (\text{mod} \ 9)$ and so on. Furthermore, we have:

$55953=5 \cdot 10^5+5 \cdot 10^3+9 \cdot 10^2+5 \cdot 10+3$

We can now reduce the digital representation of $55953$ using congruence.

\displaystyle \begin{aligned} 55953&=5 \cdot 10^5+5 \cdot 10^3+9 \cdot 10^2+5 \cdot 10+3 \\&\equiv 5 \cdot 1+5 \cdot 1+9 \cdot 1+5 \cdot 1+3 \\&=27 \\&\equiv 0 \ (\text{mod} \ 9) \end{aligned}

The above derivation shows that any positive integer is congruent modulo $9$ to the sum of its digits. Thus a positive integer is divisible by $9$ if and only if the sum of its digits is divisible by $9$.

The same property is also true for divisibility by three. Using congruence, it can be shown that any positive integer is divisible by $3$ if and only if the sum of its digits is divisible by $3$.

Congruence modulo $11$ is an interesting case. Note that $10 \equiv -1 \ (\text{mod} \ 11)$, $10^2 \equiv 1 \ (\text{mod} \ 11)$, and $10^3 \equiv -1 \ (\text{mod} \ 11)$ and so on. Thus $10^n \equiv k \ (\text{mod} \ 11)$ where $k=1$ or $k=-1$ depending on whether the power is even or odd. So in reducing the digital representation of a number, we need to add alternating plus and minus signs.

\displaystyle \begin{aligned} 85647&=8 \cdot 10^4+5 \cdot 10^3+6 \cdot 10^2+4 \cdot 10+7 \\&\equiv 8 \cdot 1+5 \cdot (-1)+6 \cdot 1+4 \cdot (-1)+7 \\&=12 \\&\equiv 1 \ (\text{mod} \ 11) \end{aligned}

Thus $85647$ is not divisible by $11$.

___________________________________________________________________________________________________________________

Exercises

Work the two congruence calculation mentioned at the beginning of the post. Show the following.

$9664^{79081} \equiv 1020 \ (\text{mod} \ 55049)$

$2^{57885161}-1 \equiv 255 \ (\text{mod} \ 524287)$

___________________________________________________________________________________________________________________

Reference

1. Dudley U., Elementary Number Theory, 2nd ed., Dover Publications, Inc, New York, 2008

___________________________________________________________________________________________________________________

$\copyright \ 2013 \text{ by Dan Ma}$

# An observation about Mersenne primes

This post concerns an observation about Mersenne primes. The observation will be made after presenting an example.

Mersenne numbers are integers of the form $M_n=2^n-1$ where $n$ is a positive integer. If $M_n$ is a prime number, then $M_n$ is said to be a Mersenne primes. Not all Mersenne numbers are prime. Are there infinitely many Mersenne primes? No one has yet been able to resolve this question. As of the writing of this post, there are only 48 known Mersenne primes, the largest of which is $M_p$ where $p=57885161$, discovered in January 25, 2013. The current largest known Mersenne prime is also the current largest known prime number.

___________________________________________________________________________________________________________________

Example

In this example, $p=57885161$. Since $M_p$ is prime, it is obviously not divisible by any other prime numbers. In particular, $M_p$ is not divisible by any smaller Mersenne primes. We demonstrate this using congruence modulo arithmetic.

We wish to point out that we are not trying to establish the primality of $M_p$ (doing that would take a great amount of super computing resources). This is merely a simple example of working with Mersenne primes and an exercise in doing congruence modulo calculation.

First, show that $M_p=2^p-1$ is not divisible by the Mersenne prime $2^{19}-1=524287$.

If $M_p=2^p-1$ is divisible by $2^{19}-1$, $M_p \equiv 0 \ (\text{mod} \ 2^{19}-1)$. So we need to show $2^p-1 \not \equiv 0 \ (\text{mod} \ 2^{19}-1)$ or $2^p \not \equiv 1 \ (\text{mod} \ 2^{19}-1)$.

Note that $2^{19} \equiv 1 \ (\text{mod} \ 2^{19}-1)$. So it is a matter of subtracting the largest multiple of 19 out of the exponent $p=57885161$. We have $p=57885161=3046587 \cdot 19+8$. We have the following congruence calculation.

$2^{57885161}=(2^{19})^{3046587} \cdot 2^8 \equiv (1)^{3046587} \cdot 2^8=2^8=256 \ (\text{mod} \ 2^{19}-1)$

Since $2^p \equiv 256 \ (\text{mod} \ 2^{19}-1)$ and $256 \ne 1$, $M_p=2^p-1$ is not divisible by $2^{19}-1=524287$.

The number $2^{3217}-1$ is also a Mersenne prime. To show that $M_p=2^p-1$ is not divisible by $2^{3217}-1$, we only need to show $2^p \not \equiv 1 \ (\text{mod} \ 2^{3217}-1)$.

Note that $2^{3217} \equiv 1 \ (\text{mod} \ 2^{3217}-1)$. We have $p=57885161=17993 \cdot 3217 + 1680$. After subtracting multiple of $3217$, we have the remainder $1680$. Thus $2^{57885161}$ congruence modulo $2^{3217}-1$ is reduced to $2^{1680}$ congruence modulo $2^{3217}-1$.

$2^{57885161} \equiv 2^{1680} \ (\text{mod} \ 2^{3217}-1)$

Since $2^{1680}>1$, $2^p \not \equiv 1 \ (\text{mod} \ 2^{3217}-1)$. Thus $M_p=2^p-1$ is not divisible by $2^{3217}-1$.

___________________________________________________________________________________________________________________

An Observation

The above examples lead to the following observation.

If $a$ and $b$ are prime numbers such that $a, then $2^a-1$ is not a divisor of $2^b-1$.

As in the examples, we need to show $2^b \not \equiv 1 \ (\text{mod} \ 2^a-1)$. Note that $2^a \equiv 1 \ (\text{mod} \ 2^a-1)$. According to the division algorithm, we have $b=r + a \cdot k$ where $k$ is some integer and $r$ is the remainder with $0 \le r . The remainder $r$ cannot be zero. If it is, $a$ would divide $b$. But this cannot be since both of them are prime numbers. Since $r \ne 0$, $2^r>1$. We have the following congruence calculation.

$2^b = (2^a)^{k} \cdot 2^r \equiv 2^r \ (\text{mod} \ 2^a-1)$

Since $2^r>1$, $2^b \not \equiv 1 \ (\text{mod} \ 2^a-1)$. Thus $2^b-1$ is not divisible by $2^a-1$.

The above derivation is definitely a much cleaner demonstration than the derivations shown in the above examples.

Another way to state the above statement is that no Mersenne number can be divisible by any smaller Mersenne number.

Note that in the above statement, $2^a-1$ and $2^b-1$ do not need to be primes. Only the exponents $a$ and $b$ need to be primes. There are many Mersenne numbers that are not prime numbers. The smallest is $2^{11}-1=28*89$. Other smaller non-prime Mersenne numbers are $2^{23}-1$ and $2^{29}-1$.

So the above statement says that even when a Mersenne number is composite, it cannot have factors of the form $2^a-1$. It can certainly not have factors in the form of a Mersenne prime. In testing whether $2^b-1$ is a prime, it can be safe to skip any smaller number of the form $2^a-1$. This fact could be useful in testing the primality of a Mersenne number (at least marginally useful).

___________________________________________________________________________________________________________________

$\copyright \ 2013 \text{ by Dan Ma}$

# How to toss a coin

In this post, we demonstrate how to simulate a random coin toss using a cryptographic algorithm that was proposed by Rivest, Shamir and Adlemen in 1982 (the creators of the RSA algorithm). Tossing a coin using a cryptographic algorithm is an example of a game of mental poker.

The term mental poker refers to the game of poker played over long distance that has a mechanism for ensuring a fair game without the need for a trusted third party. Mental poker can also refer to other cryptographic games played over long distance without the need for a trusted third party (e.g. tossing a coin over long distance).

___________________________________________________________________________________________________________________

Setting the Algorithm

A full discussion of the algorithm used here can be found in the previous post Fermat’s Little Theorem and Mental Poker.

Andy and Becky are in different locations and they would like to simulate a random coin toss. First they need to agree on two positive integers that are to represent head and tail, say $m_h$ for head and $m_t$ for tail. These two numbers should be less than the prime number $p$ discussed in the next paragraph.

They now need to encrypt the numbers before tossing the coin. Both players agree on a large prime number $p$. If the goal of preventing or minimizing cheating is important, the players should choose a prime number that is as large as feasible computationally speaking.

With the prime number $p$ decided, each of the players chooses an encryption-decryption key, which is a pair of positive integers $x_0$ and $x_1$ such that

$x_0 \cdot x_1 \equiv 1 \ (\text{mod} \ p-1)$,

meaning that $x_0 \cdot x_1=1+(p-1) \cdot k$ for some integer $k$.

Each of the players chooses such a pair of numbers. In terms of notation, Andy chooses $a_0$ and $a_1$. Becky chooses $b_0$ and $b_1$. Each player chooses the number pair independently and keeps it secret from the other player.

The number with the $0$-subscript is the encryption key and the number with the $1$-subscript is the decryption key. The following are the encryption functions, expressed in congruence modulo $p$, for Andy and Becky, respectively.

$f_a(m) \equiv m^{a_0} \ (\text{mod} \ p) \ \ \ \ \ \ \ \text{Andy}$

$f_b(m) \equiv m^{b_0} \ (\text{mod} \ p) \ \ \ \ \ \ \ \text{Becky}$

For example, if Andy wants to encrypt the number $m$, he raises $m$ to the power of $a_0$ and looks for the remainder upon division by $p$. The remainder will be denoted by $f_a(m)$. The function $f_b(m)$ works similarly for Becky.

The following are the decryption functions, expressed in congruence modulo $p$, for Andy and Becky, respectively.

$g_a(c) \equiv c^{a_1} \ (\text{mod} \ p) \ \ \ \ \ \ \ \text{Andy}$

$g_b(c) \equiv c^{b_1} \ (\text{mod} \ p) \ \ \ \ \ \ \ \text{Becky}$

For example, if Andy wants to decrypt the number $c=f_a(m)$, he raises $c$ to the power of $a_1$ and looks for the remainder upon division by $p$. The remainder will be denoted by $g_a(m)$, which will be the original number $m$. The proof of this fact is based on the Fermat’s Little Theorem (see the previous post Fermat’s Little Theorem and Mental Poker).

The function $g_b(m)$ works similarly for Becky.

___________________________________________________________________________________________________________________

A Numerical Example

For illustration, we use a small prime number. We use $p=7919$. We emphasize that this is just for illustration. In an application where the chance for cheating is to be minimized, a large prime number should be used.

Andy and Becky use the following assignment for Head and Tail.

$\displaystyle \begin{bmatrix} \text{ }&\text{ }&\text{Head}&\text{ }&\text{Tail} \\ \text{ }&\text{ }&\text{ }&\text{ }&\text{ } \\ \text{Original}&\text{ }&\text{2,500}&\text{ }&\text{5,000} \end{bmatrix}$

For this illustration, Andy chooses $a_0=\text{47}$ and $a_1=\text{52,899}$ by letting $k=\text{314}$ in the equation below. Becky chooses $b_0=\text{71}$ and $b_1=\text{26,319}$ by letting $k=\text{236}$ in the following equation.

$x_0 \cdot x_1=1+7918 \cdot k$

Andy and Becky choose these keys independently and they keep them secret without letting the other person know. Andy encrypts both the head and tail numbers as follows:

$2500^{47} \equiv 7518=f_a(2500) \ (\text{mod} \ 7919) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)$

$5000^{47} \equiv 698=f_a(5000) \ (\text{mod} \ 7919) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (2)$

The encrypted numbers and the original numbers are displayed in the following table.

$\displaystyle \begin{bmatrix} \text{ }&\text{ }&\text{Head}&\text{ }&\text{Tail} \\ \text{ }&\text{ }&\text{ }&\text{ }&\text{ } \\ \text{Original}&\text{ }&\text{2,500}&\text{ }&\text{5,000} \\ \text{ }&\text{ }&\text{ }&\text{ }&\text{ } \\ \text{Encrypted by Andy}&\text{ }&\text{7,518}&\text{ }&\text{698} \end{bmatrix}$

Of course, the above table is kept secret from Becky. However, the encrypted numbers (just the encrypted numbers) are sent to Becky for random selection.

Becky selects one of the encrypted numbers for herself (perhaps thru a coin toss). Then the other encrypted number is the choice for Andy. Suppose Becky selects $7518$. Becky then encrypted the number $7518$ using her key.

$7518^{71} \equiv 1341=f_b(7518) \ (\text{mod} \ 7919) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (3)$

Becky passes the encrypted number $1341$ (her selection) and $698$ (Andy’s selection) back to Andy. The following table lists out the numbers received by Andy.

$\displaystyle \begin{bmatrix} \text{ }&\text{ }&\text{Andy}&\text{ }&\text{Becky} \\ \text{ }&\text{ }&\text{ }&\text{ }&\text{ } \\ \text{Becky's selection}&\text{ }&\text{698}&\text{ }&\text{7,518} \\ \text{ }&\text{ }&\text{ }&\text{ }&\text{ } \\ \text{Encrypted by Becky}&\text{ }&\text{ }&\text{ }&\text{1,341} \end{bmatrix}$

Andy decrypts his number $698$ and gets back $2500$, which is tail. He also decrypts $1341$ and obtains $223$, which he passes back to Becky.

$698^{52899} \equiv 5000=g_a(698) \ (\text{mod} \ 7919) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (4)$

$1341^{52899} \equiv 223=g_a(1341) \ (\text{mod} \ 7919) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (5)$

The following summarizes the results up to this point.

$\displaystyle \begin{bmatrix} \text{ }&\text{ }&\text{Andy}&\text{ }&\text{Becky} \\ \text{ }&\text{ }&\text{ }&\text{ }&\text{ } \\ \text{Becky's selection}&\text{ }&\text{698}&\text{ }&\text{7,518} \\ \text{ }&\text{ }&\text{ }&\text{ }&\text{ } \\ \text{Encrypted by Becky}&\text{ }&\text{ }&\text{ }&\text{1,341} \\ \text{ }&\text{ }&\text{ }&\text{ }&\text{ } \\ \text{Decrypted by Andy}&\text{ }&\text{5,000}&\text{ }&\text{223} \end{bmatrix}$

Once Becky gets the decrypted number $223$ from Andy, she decrypts it using her own key to obtain $2500$, which is a head.

$223^{26319} \equiv 2500=g_b(223) \ (\text{mod} \ 7919) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (6)$

The following table summarizes the results of the coin toss.

$\displaystyle \begin{bmatrix} \text{ }&\text{ }&\text{Andy}&\text{ }&\text{Becky} \\ \text{ }&\text{ }&\text{ }&\text{ }&\text{ } \\ \text{Becky's selection}&\text{ }&\text{698}&\text{ }&\text{7,518} \\ \text{ }&\text{ }&\text{ }&\text{ }&\text{ } \\ \text{Encrypted by Becky}&\text{ }&\text{ }&\text{ }&\text{1,341} \\ \text{ }&\text{ }&\text{ }&\text{ }&\text{ } \\ \text{Decrypted by Andy}&\text{ }&\text{5,000}&\text{ }&\text{223} \\ \text{ }&\text{ }&\text{ }&\text{ }&\text{ } \\ \text{Decrypted by Becky}&\text{ }&\text{ }&\text{ }&\text{2,500} \\ \text{ }&\text{ }&\text{ }&\text{ }&\text{ } \\ \text{Results of Coin Toss}&\text{ }&\text{5,000}&\text{ }&\text{2,500} \end{bmatrix}$

___________________________________________________________________________________________________________________

Numerical Calculation

We now show some of the calculations involved in the above encryption and decryption. We show three calculations.

$5000^{47} \equiv 698=f_a(5000) \ (\text{mod} \ 7919) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (2)$

$698^{52899} \equiv 5000=g_a(698) \ (\text{mod} \ 7919) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (4)$

$223^{26319} \equiv 2500=g_b(223) \ (\text{mod} \ 7919) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (6)$

Even with the small prime number $p=7919$, the calculation is not done directly. For example, unless special software is used, $f_a(5000)$ is not found by calculating $5000^{47}$ and then finding the remainder upon division by $7919$. The following demonstrates a “divide and conquer” approach for the calculation for $(2)$ where in each step the exponent is reduced by half.

\displaystyle \begin{aligned} 5000^{47}&\equiv (5000^2)^{23} \cdot 5000 \ (\text{mod} \ 7919) \\&\text{ } \\&=7636^{23} \cdot 5000 \equiv (7636^2)^{11} \cdot 7636 \cdot 5000 \\&\text{ } \\&\equiv 899^{11} \cdot 7636 \cdot 5000 \\&\text{ } \\&\equiv 899^{11} \cdot 2501 \equiv (899^2)^5 \cdot 899 \cdot 2501 \\&\text{ } \\&\equiv 463^5 \cdot 899 \cdot 2501 \\&\text{ } \\&\equiv 463^5 \cdot 7322 \equiv (463^2)^2 \cdot 463 \cdot 7322 \\&\text{ } \\&\equiv 556^2 \cdot 463 \cdot 7322 \\&\text{ } \\&\equiv 556^2 \cdot 754 \\&\text{ } \\&\equiv 295 \cdot 754 \\&\text{ } \\&\equiv 698 \ (\text{mod} \ 7919) \end{aligned}

In each step in the above calculation, we use the division algorithm to obtain the remainder. For example, to go from the first line to the second line, divide $5000^2$ by $7919$ to obtain the remainder of $7636$. The number $698$ in the last step is the remainder when $295 \cdot 754$ is divided by $7919$. These calculations are tedious if done by hand and should be done by computer.

The calculation for $(4)$ is that $698^{52899} \equiv 5000 \ (\text{mod} \ 7919)$. In other word, decrypting the encrypted number of $698$ recovers the original number of $5000$. This calculation can be shortened by using Fermat’s Little Theorem, which implies that $698^{7919-1} \equiv 1 \ (\text{mod} \ 7919)$. Thus we have:

$698^{47508} \equiv 698^{6 \cdot 7918} \equiv 1 \ (\text{mod} \ 7919)$

So we can reduce $47508$ from the exponent $52899$, leaving the exponent $5391$. We have:

$698^{52899} \equiv 698^{47508} \cdot 698^{5391} \equiv 1 \cdot 698^{5391} \ (\text{mod} \ 7919)$

The following uses the “divide and conquer” approach to compute $698^{5391}$ modulo $7919$.

\displaystyle \begin{aligned} 698^{5391}&\equiv (698^2)^{2695} \cdot 698 \ (\text{mod} \ 7919) \\&\text{ } \\&=4145^{2695} \cdot 698 \equiv (4145^2)^{1347} \cdot 4145 \cdot 698 \\&\text{ } \\&\equiv 4714^{1347} \cdot 4145 \cdot 698 \\&\text{ } \\&\equiv 4714^{1347} \cdot 2775 \equiv (4714^2)^{673} \cdot 4714 \cdot 2775 \\&\text{ } \\&\equiv 1082^{673} \cdot 4714 \cdot 2775 \\&\text{ } \\&\equiv 1082^{673} \cdot 7081 \equiv (1082^2)^{336} \cdot 1082 \cdot 7081 \\&\text{ } \\&\equiv 6631^{336} \cdot 1082 \cdot 7081 \\&\text{ } \\&\equiv 6631^{336} \cdot 3969 \equiv (6631^2)^{168} \cdot 3969 \\&\text{ } \\&\equiv 3873^{168} \cdot 3969 \equiv (3873^2)^{84} \cdot 3969 \\&\text{ } \\&\equiv 1543^{84} \cdot 3969 \equiv (1543^2)^{42} \cdot 3969 \\&\text{ } \\&\equiv 5149^{42} \cdot 3969 \equiv (5149^2)^{21} \cdot 3969\\&\text{ } \\&\equiv 7308^{21} \cdot 3969 \equiv (7308^2)^{10} \cdot 7308 \cdot 3969 \\&\text{ } \\&\equiv 1128^{10} \cdot 7308 \cdot 3969 \\&\text{ } \\&\equiv 1128^{10} \cdot 6074 \equiv (1128^2)^{5} \cdot 6074\\&\text{ } \\&\equiv 5344^5 \cdot 6074 \equiv (5344^2)^2 \cdot 5344 \cdot 6074 \\&\text{ } \\&\equiv 2422^2 \cdot 5344 \cdot 6074 \\&\text{ } \\&\equiv2422^2 \cdot 7394 \\&\text{ } \\&\equiv 6024 \cdot 7394 \\&\text{ } \\&\equiv 5000 \ (\text{mod} \ 7919) \end{aligned}

The calculation for $(6)$ is $223^{26319} \equiv 2500 \ (\text{mod} \ 7919)$. We can also get an assist from the Fermat’s Little Theorem. In this particular case, $223^{7918} \equiv 1 \ (\text{mod} \ 7919)$. With $26319=3 \cdot 7918+2565$, we only need to calculate $223^{2565} \ (\text{mod} \ 7919)$, which is done below.

\displaystyle \begin{aligned} 223^{2565}&\equiv (223^2)^{1282} \cdot 223 \ (\text{mod} \ 7919) \\&\text{ } \\&=2215^{1282} \cdot 223 \equiv (2215^2)^{641} \cdot 223 \\&\text{ } \\&\equiv 4364^{641} \cdot 223 \equiv (4364^2)^{320} \cdot 4364 \cdot 223 \\&\text{ } \\&\equiv 7220^{320} \cdot 4364 \cdot 223 \\&\text{ } \\&\equiv 7220^{320} \cdot 7054 \equiv (7220^2)^{160} \cdot 7054 \\&\text{ } \\&\equiv 5542^{160} \cdot 7054 \equiv (5442^2)^{80} \cdot 7054 \\&\text{ } \\&\equiv 3882^{80} \cdot 7054 \equiv (3882^2)^{40} \cdot 7054 \\&\text{ } \\&\equiv 67^{40} \cdot 7054 \equiv (67^2)^{20} \cdot 7054 \\&\text{ } \\&\equiv 4489^{20} \cdot 7054 \equiv (4489^2)^{10} \cdot 7054\\&\text{ } \\&\equiv 5185^{10} \cdot 7054 \equiv (5185^2)^{5} \cdot 7054 \\&\text{ } \\&\equiv 7139^{5} \cdot 7054 \equiv (7139^2)^{2} \cdot 7139 \cdot 7054 \\&\text{ } \\&\equiv 6556^2 \cdot 7139 \cdot 7054 \\&\text{ } \\&\equiv 6556^2 \cdot 1585 \\&\text{ } \\&\equiv 4723 \cdot 1585 \\&\text{ } \\&\equiv 2500 \ (\text{mod} \ 7919) \end{aligned}

___________________________________________________________________________________________________________________

$\copyright \ 2013 \text{ by Dan Ma}$


text:
# The Unapologetic Mathematician

## Higher-Dimensional Riemann Integrals

Our coverage of multiple integrals will actually parallel our earlier coverage of Riemann integrals pretty closely. Only now we have to change our notion of “interval” to a higher-dimensional version.

For the moment, the only shapes we’ll integrate over will be closed rectangular $n$-dimensional parallelepipeds with sides parallel to the coordinate axes in $\mathbb{R}^n$. In one dimension, these are just coordinate intervals, but there aren’t many other obvious shapes to use in that case. In two dimensions, we are (for the moment) throwing out circles, ellipses, triangles, and anything else that’s not a rectangle; and even rectangles that are tilted with respect to the coordinate axes! Don’t worry, we’ll get them back later.

Anyway, such a shape in $n$-dimensional space is the product of $n$ closed intervals:

$\displaystyle[a^1,b^1]\times\dots[a^n,b^n]=\{(x^1,\dots,x^n)\in\mathbb{R}^n\vert a^1\leq x^1\leq b^1,\dots,a^n\leq x^n\leq b^n\}$

In this context, we’ll write this as $[a,b]$ for $a=(a^1,\dots,a^n)$ and $b=(b^1,\dots,b^n)$. This looks identical to, but is not to be confused with, the closed line segment from $a$ to $b$ we used in the mean value theorem. I’ll try to keep them separate by always referring to this rectangular parallelepiped as an “interval” and never using that term for a line segment. Of course, in one dimension the two are exactly the same.

Now we define a partition of an interval. We’ll do this just by partitioning each side of the interval. That is, we pick points

\displaystyle\begin{aligned}a^1={x^1}_0<&\dots<{x^1}_{m_1}=b^1\\&\vdots\\a^n={x^n}_0<&\dots<{x^n}_{m_n}=b^n\end{aligned}

where we cut the $i$th side into $m_i$ pieces, and each of the $m_i$ could be different. If we index the subintervals of the partition by $1\leq i_1\leq m_1$ through $1\leq i_n\leq m_n$, we can write

$\displaystyle I_{i_1\dots i_n}=[{x^1}_{i_1},{x^1}_{i_1+1}]\times\dots\times[{x^n}_{i_n},{x^n}_{i_n+1}]$

picking out the $i_k$th slice of the $k$th side. This cuts the whole interval up into a bunch of smaller pieces, which are themselves rectangular parallelepipeds. Again, we have the notion of a tagged partition, which picks out a sample point $t_{i_1\dots i_n}\in I_{i_1\dots i_n}$ for each subinterval. And again we say that one tagged partition is a “refinement” of another one if every partition point of the coarser partition is also one in the finer partition on the same side, and if every sample point in the coarser partition is one in the finer partition as well.

There’s a lot of numbers here and a lot of notation, but relax: most of it is going to go away very quickly. Go back and look at how partitions, tagged partitions, and refinements were defined in one variable, and just think of partitioning (and refining) the one-dimensional interval that makes up each side of the $n$-dimensional interval. Of course, like I said before, the number of parts on each side might have nothing to do with each other. Further, there’s no reason for the tags to have anything to do with each other. One might think of tagging the partition on each side of the interval, and then letting the sample points in the subintervals have those tags as coordinates. This is a perfectly valid way to come up with a collection of sample points, but the sample points don’t have to arise in this manner at all, so long as there’s exactly one within each subinterval.

So, just like in the one-dimensional case, the collection $\mathcal{P}[a,b]$ of all tagged partitions of an interval $[a,b]$ form a directed set, where we say that $P\preceq P'$ if $P'$ is a refinement of $P$. And again we define nets on this directed set; given a function $f$ defined on the interval $[a,b]$ and a partition $P\in\mathcal{P}[a,b]$, we define the Riemann sum

$\displaystyle f_P=\sum\limits_{i_1=1}^{m_1}\dots\sum\limits_{i_n=1}^{m_n}f(t_{i_1\dots i_n})\mathrm{vol}(I_{i_1\dots i_n})$

by sampling the function $f$ at the specified point $t_{i_1\dots i_n}$ in the subinterval $I_{i_1\dots i_n}$, multiplying by the $n$-dimensional volume of the subinterval (which is just the product of its side-lengths), and summing this over all the subintervals in $[a,b]$.

And again, as before, if this net converges to a limiting value $s$, we say that $f$ is Riemann integrable on the interval $[a,b]$ and we write

$\displaystyle\int\limits_{[a,b]}f\,dx=\int\limits_{[a,b]}f(x)\,dx=\int\limits_{[a,b]}f(x^1,\dots,x^n)\,d(x^1,\dots,x^n)=s$

in three different notations, depending on what we want to emphasize. The first emphasizes the function as an object in and of itself; the second, the function’s dependence on the vector variable $x$; and the third, the function’s dependence on each individual real variable. In two and three dimensions, we often write the “double integral” and “triple integral” as

\displaystyle\begin{aligned}\iint\limits_{[a,b]}&f(x)\,dx\\\iiint\limits_{[a,b]}&f(x)\,dx\end{aligned}

as visual reminders that these are multiple integrals. This gets unwieldy very quickly, and so we usually just write one integral sign for each integration.

December 1, 2009 - Posted by | Analysis, Calculus

## 10 Comments »

1. […] and Lower Integrals and Riemann’s Condition Yesterday we defined the Riemann integral of a multivariable function defined on an interval . We want to move towards […]

Pingback by Upper and Lower Integrals and Riemann’s Condition « The Unapologetic Mathematician | December 2, 2009 | Reply

2. […] an -dimensional box — an interval . Then partition this interval with some partition like we did when we set up higher-dimensional Riemann sums. Then we just count up all the subintervals in the […]

Pingback by Jordan Content « The Unapologetic Mathematician | December 3, 2009 | Reply

3. […] It asserts, simply enough, that a bounded function defined on an -dimensional interval is Riemann integrable on that interval if and only if the set of discontinuities of has measure zero. Our proof will go […]

Pingback by Lebesgue’s Condition « The Unapologetic Mathematician | December 15, 2009 | Reply

4. […] Integrals I We may remember from a multivariable calculus class that we can evaluate multiple integrals by using iterated integrals. For example, if is a continuous, nonnegative function on a […]

Pingback by Iterated Integrals I « The Unapologetic Mathematician | December 16, 2009 | Reply

5. […] this case, we’re considering integrating an integrable function over some -dimensional interval . We want something like iterated integrals […]

Pingback by Iterated Integrals IV « The Unapologetic Mathematician | December 21, 2009 | Reply

6. […] Over More General Sets To this point we’ve only discussed multiple integrals over -dimensional intervals. But often we’re interested in more general regions, like circles […]

Pingback by Integrals Over More General Sets « The Unapologetic Mathematician | December 22, 2009 | Reply

7. […] is a simple consequence of the definition of a multiple integral as the limit of Riemann sums, since every Riemann sum for will be smaller than the corresponding sum for […]

Pingback by The Mean Value Theorem for Multiple Integrals « The Unapologetic Mathematician | December 29, 2009 | Reply

8. […] this is not the differential of a variable . When it shows up in a multiple integral, it’s a tiny little bit of -dimensional volume. And we measure the scaling of -dimensional […]

Pingback by Change of Variables in Multiple Integrals I « The Unapologetic Mathematician | January 5, 2010 | Reply

9. […] a particular integrator in our Riemann-Stieltjes integral. This could also be useful in setting up multiple integrals over -dimensional intervals that extend infinitely far in some […]

Pingback by Improper Integrals II « The Unapologetic Mathematician | January 15, 2010 | Reply

10. […] together the basic -forms in order. And then on the right we suddenly switch to a -dimensional Riemann integral over the standard -cube. The canonical basis -form corresponds to the volume element , and top […]

Pingback by Integration on the Standard Cube « The Unapologetic Mathematician | August 2, 2011 | Reply


text:
SMS scnews item created by John Ormerod at Mon 4 Aug 2014 0929
Type: Seminar
Distribution: World
Expiry: 9 Aug 2014
Calendar1: 8 Aug 2014 1400-1500
CalLoc1: Carslaw 173
Auth: jormerod@pjormerod4.pc (assumed)

# Statistics Seminar: Jingjing Wu (Calgary) -- An Efficient and Robust Estimation Based on Profiling

The successful application of the Hellinger distance approach to fully
parametric models is well known. The corresponding optimal estimators,
known as minimum Hellinger distance (MHD) estimators, are efficient
and have excellent robustness properties (Beran, 1977). This combination
of efficiency and robustness makes MHD estimators appealing in practice.
However, their application to semiparametric statistical models, which
have a nuisance parameter (typically of infinite dimension), has not
been fully studied. In this talk, we investigate a methodology to
extend the MHD approach to general semiparametric models. We introduce
the profile Hellinger distance and use it to construct a minimum profile
Hellinger distance (MPHD) estimator of the finite-dimensional parameter
of interest. This approach is analogous in some sense to the profile
likelihood approach. We investigate the asymptotic properties such as
the asymptotic normality, efficiency, and adaptivity of the proposed
estimator. We also investigate its robustness properties. We present its
small-sample properties using a Monte Carlo study.

Actions:


text:
# DIVISION OF COMPLEX NUMBERS

Division of complex numbers is achieved by rationalizing with the conjugate of the denominator. That is, we multiply the numerators and denominators by the complex conjugate of the denominator.

Before we proceed, you must remember this property of imaginary number:

$i^2=-1$

With that in mind, let us try some examples.

Example 1

Solve $\frac{4+10i}{8-2i}$

Solution:

By rationalizing the denominator

$\frac{4+10i}{8-2i}\times\frac{8+2i}{8+2i}$

$\frac{4(8+2i)+10i(8+2i)}{8(8-2i)+2i(8-2i)}$

$\frac{32+8i+80i+20i^2}{64-16i+16i-4i^2}$

$\frac{32+88i+20i^2}{64-4i^2}$

If $i^2=-1$, then

$\frac{32+88i+20(-1)}{64-4(-1)}$

$\frac{32-20+88i}{64+4}$

$\frac{12+88i}{68}$

Splitting the fraction

$\frac{12}{68}+\frac{88i}{68}$

$\frac{3}{17}+\frac{22i}{17}$

Example 2

Solve $\frac{4-2i}{6+8i}$

Solution:

First, we rationalize the denominator

$\frac{4-2i}{6+8i}\times\frac{6-8i}{6-8i}$

$\frac{4(6-8i)-2i(6-8i)}{6(6-8i)+8i(6-8i)}$

$\frac{24-32i-12i+16i^2}{36-48i+48i-64i^2}$

Given that $i^2=-1$, therefore

$\frac{24-44i+16(-1)}{36-64(-1)}$

$\frac{24-16-44i}{36+64}$

$\frac{8-44i}{100}$

Splitting the fraction

$\frac{8}{100}-\frac{44i}{100}i$

$\frac{2}{25}+\frac{11}{25}i$

Example 3

Solve $\frac{3+2i}{5-i}$

Solution:

$\frac{3+2i}{5-i}\times\frac{5+i}{5+1}$

$\frac{3(5+i)+2i(5+i)}{5(5+i)-i(5+i)}$

$\frac{15+3i+10i+2i^2}{25-i^2}$

Recalled that $i^2=-1$

$\frac{15+13i+2(-1)}{25-(-1)}$

$\frac{15-2+13i}{26}$

$\frac{13+13i}{26}$

Splitting the fraction

$\frac{13}{26}+\frac{13}{26}i$

$\frac{1}{2}+\frac{1}{2}i$

Example 4

If $z_1=1-3i$, $z_2=-2+5i$ and $z_3=-3-4i$. Find

i. $\frac{Z_1}{Z_3}$

ii. $\frac{Z_1Z_2}{Z_1+Z-2}$

Solution:

I. By substitution

$\frac{1-3i}{-3-4i}$

Now, let's rationalize the denominator

$\frac{1-3i}{-3-4i}\times\frac{-3+4i}{-3+4i}$

$\frac{1(-3+4i)-3i(-3+4i)}{9-16i^2}$

$\frac{-3+4i+9i-12i^2}{9-16(-1)}$

$\frac{-3+13i+12}{25}$

$\frac{9+13i}{25}$

$\frac{9}{25}+\frac{13}{25}i$

ii. To solve this, we have to evaluate the numerator and denominator separately.

we know that $z_1=1-3i$, $z_2=-2+5i$, hence

$(1-3i)(-2+5i)$

So, let's multiply these complex numbers

$1(-2+5i)-3i(-2+5i)$

$-2+5i+6i-15i^2$

$-2+11i+15$

$13+11i$

Now, to the denominator...

$(1-3i)+(-2+5i)$

So, let add these complex numbers

$(1-2)+(-3i+5i)$

$-1+2i$

Now, let evaluate together

$\frac{13+11i}{1+2i}$

By rationalizing the denominator

$\frac{13+11i}{-1+2i}\times\frac{-1-2i}{-1-2i}$

$\frac{13(-1-2i)+11i(-1-2i)}{5}$

$\frac{-13-26i-11i-22i^2}{5}$

if $i^2=-1$, then

$\frac{-13+22 -26i-11i}{5}$

$\frac{9-37i}{5}$

$\frac{9}{5}-\frac{37}{5}i$

That is all for now. Got questions relating to this? tell me in the comment box.

Help us grow our readership by sharing this post