The spatial shift in the PDF also requires a boundary value beyond the supplied right endpoint: if is the last interior index, the newest value is outside the interval. Thus the printed Dirichlet method has no specified boundary closure, and no unique stability range can be assigned to it as stated.
For completeness, the literal interior formula has an exact von Neumann stability analysis on an infinite or periodic grid. Substitution of a Fourier mode gives
For the root of a polynomial tending to one as , expansion gives
Consequently is unstable: sufficiently small nonzero frequencies have a root of a polynomial of modulus greater than one, and arbitrarily fine periodic grids contain such frequencies.
Conversely, if and , then
For with ,
Since , the complex quadratic Schur criterion yields both roots of a polynomial in the unit disk, strictly inside except at , where they are and . Uniform stability follows directly from the BDF2 discrete energy identity: the modal recurrence is , whose energy decreases because . Summing the modal energies proves a bound independent of the grid and even of ; no eigenvector-separation assumption is needed. This is the stability of a spatially shifted BDF2 stencil. Thus the literal periodic-grid result is
This cannot establish stability of an unspecified Dirichlet boundary condition closure. It also does not restore consistency of a numerical method.
For the intended unshifted backward differentiation formula, a spatial eigenvalue gives
The Schur stability criterion gives the root condition for a multistep method for every , with strict inequalities for . A useful uniform energy method proof, including the repeated interior roots that a bare separation argument would miss, is the BDF2 discrete energy identity. With and
the corrected Dirichlet discrete Laplacian scheme satisfies
This follows by taking the inner product of with and using summation by parts. It controls both time levels uniformly, regardless of the mesh ratio. Hence the corrected method is stable for
A Runge-Kutta method advances through stages
The Butcher tableau records , normally with . Linear absolute stability tests the amplification of a linear decay mode; nonlinear B-stability compares distances between two solutions of a dissipative vector field. Both describe propagation of perturbations, but they impose different conditions.
For the Dahlquist test equation, elimination of stages gives
The linear stability domain consists of for which the step is defined and . Poles or singular stage systems must be excluded, even if an output formula has a formal cancellation. For a scalar test equation, the proof is : the powers are bounded exactly when . For , the update is . If is a normal matrix, unitary diagonalization of a normal matrix makes the operator norm equal to the largest scalar amplification modulus. For a diagonalizable matrix, powers are bounded by the condition number of the eigenvector matrix times the maximal scalar power. These constants must remain uniform for mesh-dependent systems. A defective unit-modulus eigenvalue can instead produce a growing Jordan block; the scalar spectral test alone does not control a general matrix.
An A-stable method accepts the entire closed left half-plane. The Explicit Euler method has and a disk of stability , so it is not A-stable. No nonconstant polynomial stability function can be A-stable, since it is unbounded on the negative real axis; this excludes all consistent explicit Runge-Kutta methods. The Backward Euler method has , and when , proving A-stability. It is also L-stable, because for large left-half-plane .
The implicit midpoint rule and the trapezoidal rule have the same scalar stability function,
The identity proves A-stability. On the imaginary axis their amplification has unit modulus, and along the negative real axis it tends to . Thus neither is L-stable; very stiff decay can persist as alternating numerical values. In contrast, the two-stage Radau IIA method has , with the explicit nonnegative modulus-gap proof in question 1, and is L-stable. This illustrates why L-stability matters beyond A-stability for a stiff differential equation.
For nonlinear problems, assume a real or complex Euclidean inner product and the dissipativity hypothesis
for all relevant states at each common time. Exact solutions satisfy
A B-stable Runge-Kutta method reproduces this nonexpansion of distances whenever its stages exist. Put , , and . Then . Expansion of the output squared norm, followed by substituting in its linear terms, proves the Runge-Kutta contractivity identity
If and is a positive semidefinite matrix, the first sum is nonpositive by dissipativity, and the second is nonnegative: expand each coordinate of the stage vectors to express it as a sum of nonnegative quadratic forms. These are exactly the conditions for algebraic stability of a Runge-Kutta method. Hence algebraic stability implies B-stability. Applying B-stability to the linear dissipative problem , or its two-dimensional real form, also proves A-stability whenever stages are well defined.
The Backward Euler method has , hence ; the implicit midpoint rule has , , hence . Both are algebraically stable and B-stable. For the two-stage Radau IIA method,
a positive semidefinite matrix, while both weights are positive. It therefore combines third-order accuracy, B-stability, and L-stability. The distinction between stability and solvability is essential: for Lipschitz continuous , the stage map is a contraction when , so the contraction mapping theorem proves small-step unique solvability. The preceding algebraic stability proof is an estimate for existing stages; it is not a theorem asserting stage existence for arbitrary step sizes and domains.
Linear A-stability is insufficient for nonlinear B-stability. The trapezoidal rule fails B-stability, even though its scalar stability function is identical to that of the B-stable implicit midpoint rule. Its Runge-Kutta method coefficients are
Failure of this sufficient algebraic stability test alone would not prove failure of B-stability. An actual counterexample does: take and . Dissipativity follows from
The unique step map obeys , because the left-hand side is strictly increasing and onto. At , , and implicit differentiation gives
Nearby initial states expand in distance. This proves a true nonlinear failure rather than merely failure of a coefficient criterion.
Finally, stability of a numerical method on finite intervals connects these contractivity properties to accuracy. If a one-step map is nonexpansive and its exact one-step defect has norm at most , then the error satisfies , hence for . A Lipschitz step bound gives the same order using the discrete Gronwall inequality. For a stiff differential equation, the value of B-stability is that the propagation estimate need not grow with a large negative dissipative rate. The accuracy constant still needs appropriate smoothness and uniform derivative bounds; stability alone does not establish a mesh-uniform error order.
For a fully discrete linear partial differential equation evolution, write in a specified discrete norm. Finite-time stability of a numerical method means
with independent of the allowed meshes. For a multistep method, augment the state with its time-history values and include a stable starter. Bounds may grow as when the continuous problem has growth; demanding decay for all time would be a stronger assertion. The treatment of initial data, forcing, Dirichlet boundary conditions, and the norm is part of the hypothesis, not a detail supplied by an interior calculation.
For constant coefficients on an infinite or periodic uniform grid, von Neumann stability analysis substitutes the Fourier mode . The discrete Fourier transform and the Parseval identity turn a uniform multiplier estimate into a discrete L2 norm estimate. In a one-step scalar scheme, proves contractivity, while gives finite-time stability. In a multilevel scheme, every root of a polynomial in its amplification polynomial of a multilevel finite difference scheme matters, as does uniform control of the associated companion matrix.
For the Forward Euler diffusion scheme with ,
Thus for all frequencies exactly when
Sufficiency follows since ; necessity follows from the highest-frequency mode on even periodic grids. This gives the usual parabolic mesh restriction . For the Backward Euler diffusion scheme,
so every is stable. The Crank-Nicolson method has
again of modulus at most one for all , but stiff modes approach rather than zero. These are PDE manifestations of the A-stability and L-stability distinctions for time integration.
For advection , assume and set . The upwind finite difference scheme is , with
It is contractive when . This also has a direct maximum-norm proof: each newest value is a convex combination of two old values. The resulting Courant–Friedrichs–Lewy condition expresses that the numerical domain of dependence covers the physical one. For negative , the upwind direction must be reversed. By contrast, Forward Euler method time stepping with the centered first finite difference has and for nonzero . Under fixed nonzero refinement it is unstable, since a fixed nontrivial mode grows geometrically over steps. This is not a claim of instability under every imaginable mesh coupling: instead bounds its spurious finite-time growth, since .
The leapfrog advection scheme illustrates a multilevel subtlety. Its amplification polynomial of a multilevel finite difference scheme is
For , both roots of a polynomial have unit modulus and separation at least . A uniformly conditioned eigenbasis of the companion matrix then proves power boundedness of a two-level Fourier scheme for arbitrary history data. At and a grid admitting , the roots coincide on the unit circle, and a Jordan block produces growth. Thus the endpoint fails the ordinary arbitrary-history root condition for a multistep method; checking only that both moduli equal one misses the instability. Restricting the starter or filtering the parasitic mode is an additional hypothesis.
The energy method handles variable coefficients and finite boundaries for which Fourier stability analysis may be unavailable. For the Backward Euler diffusion scheme with homogeneous Dirichlet boundary conditions, define . The discrete summation by parts identity is
Take the inner product of with . The elementary identity gives
This proves unconditional contractivity including the actual boundary treatment. More generally, a dissipative operator gives of operator norm at most one: with , dissipativity implies , and the Cauchy-Schwarz inequality gives . In finite dimensions this also proves invertibility. For the second-order backward differentiation formula, the BDF2 discrete energy identity used in question 4 controls both time levels and proves unconditional diffusion stability. A repeated root strictly inside the disk is harmless here; the energy argument supplies the uniform bound without a singular eigenvector formula.
A second technique is eigenvalue stability analysis of a finite difference method. Under the method of lines, a time integrator advances by . If is a normal matrix, the scalar linear stability domain criterion on all controls its powers exactly in the corresponding L2 norm. For the centered Dirichlet discrete Laplacian, its eigenvalues lie between and zero; intersecting this interval with a time integrator's stability interval determines its mesh restriction. A uniform bound on the diagonalization of a matrix is needed for nonnormal diagonalizable systems. Eigenvalues alone can be misleading. For example,
has both eigenvalues inside the disk for , but the upper-right entry of is . Taking , , this grows like . Hence stable scalar eigenvalues do not give mesh-uniform stability. Boundary closures can introduce precisely the extra growth that an interior Fourier symbol overlooks, so boundary stability of a finite-difference method must be checked separately.
For nonlinear spatial discretizations, a useful replacement for Fourier stability analysis is a convexity argument. If the Forward Euler method map is nonexpansive in a chosen norm for , the second-order strong stability preserving Runge-Kutta method
is also nonexpansive under the same restriction. Indeed, for two inputs, the triangle inequality gives . Its Taylor expansion is , proving order two. Such strong stability preserving Runge-Kutta methods transfer suitable forward-step bounds without relying on a linear spectral calculation.
Finally, consistency of a numerical method explains what stability buys. For a linear Hadamard well-posed problem, the Lax equivalence theorem equates convergence of a consistent discretization with its stability, under the stated approximation-space and norm hypotheses. Directly, if the error satisfies , iteration gives the discrete Duhamel principle
Thus vanishing normalized local truncation error and initial error yield convergence. With a nonlinear Lipschitz step estimate, the discrete Gronwall inequality plays the same role. A stable but inconsistent stencil, such as the literal defective formulas in questions 3 and 4 under their usual refinement, is not rescued by any amplification bound. The decisive checks are a mesh-uniform evolution bound, a valid boundary closure, and consistency with the actual PDE.
A fraction of adults survives each time step; is the adult mortality fraction. Adults produce larvae, which mature one step later with recruitment reduced by adult-dependent competition through . Eliminating larvae gives the second-order difference equation
At an equilibrium point, either or
Only nonnegative populations are admissible. At extinction the Jacobian matrix is and its characteristic polynomial is . Its positive root exceeds exactly when . For both roots have modulus less than ; at the roots are , so linearization is marginal. On the nonnegative state space extinction is still attracting at this equality: if two consecutive adult values are bounded by , the next is at most , with strict decrease away from zero; the maximum of two consecutive adult values strictly decreases after two steps whenever it is positive; continuity on its bounded state region then excludes a positive limiting maximum. Thus the extinction equilibrium point is unstable exactly when the positive equilibrium point exists, with equality understood through nonlinear rather than strict linear stability.
At the positive equilibrium point, the trace and determinant of the Jacobian matrix are and . The Jury stability criterion for requires , and . The strict linear stability analysis conditions are
For there is no upper bound on ; for the stable region is .
Figure 1.
Stability regions and equilibrium branches
. Details.
At the lower boundary , the positive equilibrium point merges with extinction, with a multiplier and slow recovery. At the upper boundary a multiplier reaches (the other is ), giving alternating adult/larval fluctuations. The nonlinear map confirms a supercritical period-doubling bifurcation, as follows. For , put and . A nonconstant period-two adult sequence satisfies and . Subtracting and adding these equations gives
Thus positive unequal values emerge for , with amplitude proportional to . The two larval phases are . If are the trace and determinant of the two-step Jacobian matrix, direct multiplication gives
At onset and , so the other two strict Jury stability criterion inequalities hold for sufficiently small positive . Hence just beyond the upper boundary, a stable period-two population cycle replaces the stable equilibrium. This is a local conclusion, not stability for arbitrarily large reproduction rates.
At the upper boundary itself, the positive equilibrium point is still locally asymptotically stable, despite its multiplier . To decide this equality case, apply the centre manifold theorem for a discrete dynamical system. Put and write the centre graph as with . If the reduced map is , its invariance equation is . Expanding the original recruitment map and this equation through cubic order gives
Consequently . The stability at a nondegenerate flip bifurcation criterion shows algebraic attraction on the centre direction; the transverse multiplier has modulus less than one. Including this boundary, the complete local asymptotic-stability condition for a positive population is therefore
The shaded figure shows the strict linear-stability region; its upper boundary adds this nonhyperbolic attracting case.
Demographic stochasticity near the lower boundary can lead to absorption at extinction; near the upper boundary it excites alternating fluctuations and can blur the deterministic period-doubling bifurcation. These qualitative predictions depend on the chosen stochastic recruitment and mortality rules.
For ,
Matching its modulus and complex argument with gives
The characteristic polynomial of the displayed rotation matrix is , so its eigenvalues are , all of modulus one. The real eigenvector spans the rotation axis, while the arguments of the conjugate eigenvalues record the rotation angle on its perpendicular plane.
Applying first the -rotation and then the -rotation gives
Its -eigenspace is spanned by , so . The matrix trace identity gives . Thus .
Use the canonical Kähler potential and normalize superspace integration by . The superspace Lagrangian density is
The full superspace integration produces a D-term, while the chiral superfield integral produces an F-term. Work in chiral coordinates for the chiral-superfield component expansion, so the omitted spacetime-derivative terms do not enter the extraction of .
Set . A Taylor expansion of the superpotential gives
Higher terms vanish because there are only two Grassmann variables . With and , their anticommutation gives . Thus
The canonical Kähler potential contributes . Consequently the part of the Lagrangian density containing the auxiliary field is
The fermion terms coming from the superpotential are
The Weyl spinor kinetic term and the complex scalar field kinetic term are canonical because .
Treat and as independent variables in their algebraic Euler-Lagrange equations. They give
Equivalently,
After eliminating the auxiliary field, the Lagrangian density contains , so the F-term scalar potential is
It is nonnegative for arbitrary complex , since it is a modulus squared. A supersymmetric vacuum satisfies F-flatness, so its zeros are:
If and these coincide; if and only the origin remains; if every constant is a supersymmetric vacuum.
To compare masses, expand around a supersymmetric vacuum satisfying , writing . With ,
Writing gives the scalar field mass term ; the Weyl spinor has physical mass . Therefore the supersymmetric mass degeneracy is
In particular, at the boson and fermion masses are both . At the second supersymmetric vacuum the sign of reverses, but the physical mass is again . Equality here concerns fluctuations about a supersymmetric vacuum, not arbitrary backgrounds with .
In the convention and , the same superpotential coefficient gives and . The supersymmetric relation between quartic and Yukawa couplings is therefore
If instead the Yukawa interaction is written , then and the same physical relation is . The numerical factor depends on the definition of the Yukawa coupling.
The perturbative non-renormalization theorem applies to the local holomorphic superpotential in the Wilsonian effective action, using regularization in quantum field theory that preserves supersymmetry. There are two complementary ways to see why it applies here.
First, in supergraph calculations in perturbative quantum field theory, the algebra of supersymmetric covariant derivatives puts any candidate local correction to the superpotential into a full superspace integration. It therefore corrects a D-term, such as the Kähler potential, rather than a local chiral F-term. Turning such a contribution into an apparent chiral integral would require nonlocal inverse spacetime derivatives, schematically . These are excluded from the local Wilsonian effective action with a fixed nonzero momentum cutoff. This gives the diagrammatic non-renormalization theorem.
Second, the holomorphy argument for superpotential non-renormalization treats and as background chiral spurions, so the Wilsonian effective action superpotential is a holomorphic function of , with no dependence on or . Assign an ordinary spurion charge and an R-charge as follows:
The superpotential has ordinary charge zero and R-charge two, since has R-charge minus two. A prospective holomorphic monomial must therefore satisfy
For perturbative corrections, regularity at and requires nonnegative powers of the couplings. Regularity in is justified by keeping a nonzero Wilsonian momentum cutoff and retaining as a light field. Hence only and survive: the existing and structures. The quadratic coefficient is fixed by the free theory at , where there are no interaction loops. The cubic coefficient is fixed at first order in , where a connected three-field interaction has only its tree-level Feynman diagram; loop corrections would require further powers of the interaction couplings, which the holomorphy argument for superpotential non-renormalization charge constraints forbid. Thus
A field-independent constant is physically irrelevant in this rigid model; the spurion charges would in any case require , which is not regular at .
The Kähler potential can still receive wave-function renormalization. For example, gives the canonical field normalization , and consequently
These canonically normalized parameters can run with the renormalization scale; this does not contradict the holomorphic non-renormalization theorem. When massless modes are included in the full quantum effective action, nonlocal terms associated with infrared divergences can also imitate an F-term. Distinguishing that action from the local Wilsonian effective action is part of the theorem's convention.
The orthogonal group is
The special orthogonal group is its determinant-one subgroup
Every eigenvalue of an orthogonal matrix has modulus one. A real three-by-three matrix has at least one real eigenvalue, and nonreal eigenvalues occur in a complex conjugate pair. If has such a pair , their product is one, so the remaining eigenvalue is . If all three eigenvalues are real, each is and their product is one; an odd number of three signs with product one must include . Hence every element of has an eigenvector of eigenvalue one and represents a rotation in three dimensions about its span.
It is false that every element of is either a rotation or a plane reflection. For example,
is an improper orthogonal transformation combining a rotation with a reflection. Its eigenvalues are and , whereas a plane reflection has eigenvalues and a rotation has determinant one.
Measure the coset state in the common eigenbasis of the group shift operators. Its overlap is
The character-sum cancellation lemma makes this sum when is trivial on , and zero otherwise. Hence, with the annihilator of a subgroup of a finite abelian group,
Since , this is the uniform distribution on a finite set . The factor has modulus one, so the distribution is independent of . This is abelian hidden-subgroup Fourier sampling.
For a Fourier mode, the amplification polynomial is
Put and . The roots become
If , the square root is real, both roots have modulus one, and their separation is at least . The companion matrix has eigenvectors , so their uniform separation gives a mesh-independent bound on its powers. By power boundedness of a two-level Fourier scheme and the discrete Fourier transform, this proves stability for .
If , choose . The roots have product of modulus one and unequal moduli, so one has modulus greater than one. The scheme is unstable.
The boundary cases require more than a root-modulus check. At , gives , while gives . The companion matrices have nontrivial Jordan blocks and solutions of the form . Their linear growth rules out a uniform stability bound. This mode occurs on even periodic grids, which are enough to disprove mesh-uniform stability at the endpoints.
Therefore the stable range is exactly
Within this range, second-order convergence additionally requires two appropriately accurate starting time levels. The unit-modulus parasitic root near does not decay, so poor initialization cannot be repaired by the scheme.
The one-dimensional Time-dependent Schrödinger equation for a wavefunction in a real potential is
Multiplying this equation by , multiplying its complex conjugate by , and subtracting gives the probability continuity equation
If and its first derivative decay sufficiently rapidly as , then the probability current vanishes at both ends. Integrating the continuity equation and using the fundamental theorem of calculus yields
This conservation of quantum probability is required by the Born rule: once a normalizable wavefunction has total probability one, its time evolution must preserve that normalization.
For the stated Gaussian wave packet, put . Since
its squared modulus is
The Gaussian integral then gives
which is independent of time, as required.
Taking the squared modulus and using gives
The incident wavevector makes an angle with the downward vertical, so . Substitution gives the required formula.
Rouché's theorem states that if and are holomorphic functions on a neighbourhood of the closure of a bounded domain and
on its positively oriented boundary, then and have the same number of zeros in the domain, counted with multiplicity.
The Open mapping theorem states that a nonconstant holomorphic function on a domain maps every open subset to an open subset. To prove it, fix and put . By the identity theorem, the zeros of are isolated. Choose so that the closed disc lies in the domain and is the only zero of in that disc. Then
Whenever , the constant has modulus smaller than on the circle. The Rouche theorem therefore says that
has the same positive number of zeros in the disc as . Thus every lies in the image of , proving that the image is open.
If had a local maximum at , take a small open disc on which . The restriction of to cannot be constant, since the identity theorem would then make constant on the whole domain. The complex open mapping theorem says that is an open neighbourhood of , and such a neighbourhood contains points of modulus greater than , a contradiction. This proves the maximum modulus principle from the complex open mapping theorem.
Now let be bounded. Its closure is compact, so the continuous function attains a maximum there. If is nonconstant, the maximum modulus principle excludes an interior maximum; if is constant, the claimed bound is immediate. Hence
which is the maximum modulus principle on a bounded domain.
Finally let and suppose throughout . Fix . The principal complex logarithm is holomorphic on the right half-plane, so for each positive integer the function
is holomorphic on and continuous on its closure. Given , choose so large that
Apply the bounded-domain result to on . On the vertical part of the boundary, and hence . On the circular part,
It follows that
Letting and then gives . Since was arbitrary, this proves the bounded half-plane maximum principle.
The boundedness assumption is necessary. The function
is holomorphic on and continuous on its closure, and on the boundary, but is unbounded for real . Thus the boundary estimate does not control an unbounded holomorphic function on this unbounded domain.
Let
be reflection in the unit circle, and represent a Möbius transformation by
A direct calculation shows that is represented by
Thus exactly when and differ by a nonzero scalar. Applying the conjugate-linear involution twice shows that this scalar has modulus one. Rescaling by a suitable complex scalar then makes . Consequently all commuting maps, and only those maps, have the form
This is the Möbius maps commuting with reflection in the unit circle classification.
For such a map,
It follows that whenever precisely when
The inverse has the same property, so these and only these maps preserve the unit disc.
For a slowly varying envelope , the paraxial approximation to the Helmholtz equation is
Because and , passage through a sufficiently thin phase screen produces
Its modulus is one at the screen exit. Beyond the screen, , so the parabolic wave equation is . A Taylor expansion in propagation distance gives
Since
we find
It follows that
or, equivalently, . Thus random phase curvature produces local focusing and defocusing: free-space diffraction converts phase fluctuations into amplitude fluctuations immediately after the screen.
The reflected P-wave is propagating only while its normal wavenumber is real, equivalently while . Since
it is evanescent when
Put
Then its spatial factor is
which decays as . The reflected SV amplitude becomes
The numerator and denominator have equal complex modulus, so
Thus evanescent mode conversion changes the reflected SV phase but not its amplitude, as described by Unit-modulus SV reflection with evanescent P conversion.
The travelling-wave substitution gives
Write
Its real part satisfies
For , the imaginary part also gives
With and a translation chosen so that the notch is centred at zero,
Its limiting modulus is , as required. The same expression at is obtained directly from the second-order equation.
The special orthogonal group is
If
its first column is a unit vector, say . The second column is the unique unit vector perpendicular to it that gives positive determinant, namely . Thus
so is rotation through about the origin.
For , its real characteristic polynomial of odd degree has a real eigenvalue. Every eigenvalue of an orthogonal matrix has modulus one, so every real eigenvalue is . Nonreal eigenvalues occur in conjugate pairs whose product is one, while ; if all eigenvalues are real, their product likewise forces at least one to be . Hence fixes a nonzero vector . The plane is -invariant, and the restriction to it is an orientation-preserving orthogonal map. By the result it is a planar rotation. Therefore is a rotation about the axis .
An algebraic number is an algebraic integer when it is a root of a monic polynomial in .
If and are algebraic integers, the ring is a finitely generated -module. Multiplication by preserves this module, so the algebraic integer module criterion shows that is an algebraic integer.
The ring of integers of a quadratic field gives
since . For a direct verification, if with is integral, then its trace and norm are integers. Writing and reducing the norm condition in lowest terms shows first that can have denominator at most ; a denominator with odd numerator would require , which is impossible. Thus , and then the norm condition forces even, so . Conversely, every with is integral because is integral and algebraic integers form a ring.
Now let have degree and roots . Since
and , the integer cannot be ; hence . Thus is monic up to sign and is an algebraic integer.
Let be the product of all roots with modulus greater than one, counting multiplicity. Complex roots occur in conjugate pairs, so is real up to the signs of the real roots and
As a product of algebraic integers, is an algebraic integer; the equality forces . Therefore
is the absolute value of the product of the remaining conjugates, is rational, and is an algebraic integer. It is consequently a nonzero rational integer. Every remaining factor has modulus at most one, so this integer is at most one. It must equal one, and hence
This is the mahler-measure norm argument at measure two.
Let the intercepted ciphertexts be
Since , the extended Euclidean algorithm gives integers with . The common-modulus RSA attack recovers
Negative powers are evaluated using modular inverses. If an inverse does not exist, its greatest common divisor with already factors the modulus.