Number Theory Commons^™

Optimizing Buying Strategies In Dominion, Nikolas A. Koutroulakis

Rose-Hulman Undergraduate Mathematics Journal

Dominion is a deck-building card game that simulates competing lords growing their kingdoms. Here we wish to optimize a strategy called Big Money by modeling the game as a Markov chain and utilizing the associated transition matrices to simulate the game. We provide additional analysis of a variation on this strategy known as Big Money Terminal Draw. Our results show that player's should prioritize buying provinces over improving their deck. Furthermore, we derive heuristics to guide a player's decision making for a Big Money Terminal Draw Deck. In particular, we show that buying a second Smithy is always more optimal …

Further Generalizations Of Happy Numbers, E. Simonton Williams

Rose-Hulman Undergraduate Mathematics Journal

A positive integer n is defined to be happy if iteration of the function taking the sum of the squares of the digits of n eventually reaches 1. In this paper we generalize the concept of happy numbers in several ways. First we confirm known results of Grundman and Teeple and establish further results extending the known structure of happy numbers to higher powers. Then we construct a similar function expanding the definition of happy numbers to negative integers. Working with this function, we prove a range of results paralleling those already proven for traditional and generalized happy numbers. Finally, …

Divisibility Probabilities For Products Of Randomly Chosen Integers, Noah Y. Fine

Rose-Hulman Undergraduate Mathematics Journal

We find a formula for the probability that the product of n positive integers, chosen at random, is divisible by some integer d. We do this via an inductive application of the Chinese Remainder Theorem, generating functions, and several other combinatorial arguments. Additionally, we apply this formula to find a unique, but slow, probabilistic primality test.

Some Thoughts On The 3 × 3 Magic Square Of Squares Problem, Desmond Weisenberg

Rose-Hulman Undergraduate Mathematics Journal

A magic square is a square grid of numbers where each row, column, and long diagonal has the same sum (called the magic sum). An open problem popularized by Martin Gardner asks whether there exists a 3×3 magic square of distinct positive square numbers. In this paper, we expand on existing results about the prime factors of elements of such a square, and then provide a full list of the ways a prime factor could appear in one. We also suggest a separate possible computational approach based on the prime signature of the center entry of the square.

On Isomorphic K-Rational Groups Of Isogenous Elliptic Curves Over Finite Fields, Ben Kuehnert, Geneva Schlafly, Zecheng Yi

Rose-Hulman Undergraduate Mathematics Journal

It is well known that two elliptic curves are isogenous if and only if they have same number of rational points. In fact, isogenous curves can even have isomorphic groups of rational points in certain cases. In this paper, we consolidate all the current literature on this relationship and give a extensive classification of the conditions in which this relationship arises. First we prove two ordinary isogenous elliptic curves have isomorphic groups of rational points when they have the same $j$-invariant. Then, we extend this result to certain isogenous supersingular elliptic curves, namely those with equal $j$-invariant of either 0 …

Structure Of Number Theoretic Graphs, Lee Trent

Mathematical Sciences Technical Reports (MSTR)

The tools of graph theory can be used to investigate the structure
imposed on the integers by various relations. Here we investigate two
kinds of graphs. The first, a square product graph, takes for its vertices
the integers 1 through n, and draws edges between numbers whose product
is a square. The second, a square product graph, has the same vertex set,
and draws edges between numbers whose sum is a square.
We investigate the structure of these graphs. For square product
graphs, we provide a rather complete characterization of their structure as
a union of disjoint complete graphs. For …

A Proof Of A Generalization Of Niven's Theorem Using Algebraic Number Theory, Caroline Nunn

Rose-Hulman Undergraduate Mathematics Journal

Niven’s theorem states that the sine, cosine, and tangent functions are rational for only a few rational multiples of π. Specifically, for angles θ that are rational multiples of π, the only rational values of sin(θ) and cos(θ) are 0, ±½, and ±1. For tangent, the only rational values are 0 and ±1. We present a proof of this fact, along with a generalization, using the structure of ideals in imaginary quadratic rings. We first show that the theorem holds for the tangent function using elementary properties of Gaussian integers, before extending the approach to other imaginary quadratic rings. We …

Probability Distributions For Elliptic Curves In The Cgl Hash Function, Dhruv Bhatia, Kara Fagerstrom, Max Watson

Mathematical Sciences Technical Reports (MSTR)

Hash functions map data of arbitrary length to data of predetermined length. Good hash functions are hard to predict, making them useful in cryptography. We are interested in the elliptic curve CGL hash function, which maps a bitstring to an elliptic curve by traversing an inputdetermined path through an isogeny graph. The nodes of an isogeny graph are elliptic curves, and the edges are special maps betwixt elliptic curves called isogenies. Knowing which hash values are most likely informs us of potential security weaknesses in the hash function. We use stochastic matrices to compute the expected probability distributions of the …

Irreducibility And Galois Groups Of Random Polynomials, Hanson Hao, Eli Navarro, Henri Stern

Rose-Hulman Undergraduate Mathematics Journal

In 2015, I. Rivin introduced an effective method to bound the number of irreducible integral polynomials with fixed degree d and height at most N. In this paper, we give a brief summary of this result and discuss the precision of Rivin's arguments for special classes of polynomials. We also give elementary proofs of classic results on Galois groups of cubic trinomials.

Disjointness Of Linear Fractional Actions On Serre Trees, Henry W. Talbott

Rose-Hulman Undergraduate Mathematics Journal

Serre showed that, for a discrete valuation field, the group of linear fractional transformations acts on an infinite regular tree with vertex degree determined by the residue degree of the field. Since the p-adics and the polynomials over the finite field of order p act on isomorphic trees, we may ask whether pairs of actions from these two groups are ever conjugate as tree automorphisms. We analyze permutations induced on finite vertex sets, and show a permutation classification result for actions by these linear fractional transformation groups. We prove that actions by specific subgroups of these groups are conjugate only …

A Case Study On Hooley's Conditional Proof Of Artin's Primitive Root Conjecture, Shalome Kurian

Rose-Hulman Undergraduate Mathematics Journal

Artin’s Primitive Root Conjecture represents one of many famous problems in elementary number theory that has resisted complete solution thus far. Significant progress was made in 1967, when Christopher Hooley published a conditional proof of the conjecture under the assumption of a certain case of the Generalised Riemann Hypothesis. In this survey we present a description of the conjecture and the underlying algebraic theory, and provide a detailed account of Hooley’s proof which is intended to be accessible to those with only undergraduate level knowledge. We also discuss a result concerning the qx+1 problem, whose proof requires similar techniques to …

Mathematical Magic: A Study Of Number Puzzles, Nicasio M. Velez

Rose-Hulman Undergraduate Mathematics Journal

Within this paper, we will briefly review the history of a collection of number puzzles which take the shape of squares, polygons, and polyhedra in both modular and nonmodular arithmetic. Among other results, we develop construction techniques for solutions of both Modulo and regular Magic Squares. For other polygons in nonmodular arithmetic, specifically of order 3, we present a proof of why there are only four Magic Triangles using linear algebra, disprove the existence of the Magic Tetrahedron in two ways, and utilizing the infamous 3-SUM combinatorics problem we disprove the existence of the Magic Octahedron.

The Name Tag Problem, Christian Carley

Rose-Hulman Undergraduate Mathematics Journal

The Name Tag Problem is a thought experiment that, when formalized, serves as an introduction to the concept of an orthomorphism of $\Zn$. Orthomorphisms are a type of group permutation and their graphs are used to construct mutually orthogonal Latin squares, affine planes and other objects. This paper walks through the formalization of the Name Tag Problem and its linear solutions, which center around modular arithmetic. The characterization of which linear mappings give rise to these solutions developed in this paper can be used to calculate the exact number of linear orthomorphisms for any additive group Z/nZ, which is demonstrated …

New Theorems For The Digraphs Of Commutative Rings, Morgan Bounds

Rose-Hulman Undergraduate Mathematics Journal

The digraphs of commutative rings under modular arithmetic reveal intriguing cycle patterns, many of which have yet to be explained. To help illuminate these patterns, we establish a set of new theorems. Rings with relatively prime moduli a and b are used to predict cycles in the digraph of the ring with modulus ab. Rings that use Pythagorean primes as their modulus are shown to always have a cycle in common. Rings with perfect square moduli have cycles that relate to their square root.

On Consecutive Triples Of Powerful Numbers, Edward Beckon

Rose-Hulman Undergraduate Mathematics Journal

A powerful number is a positive integer such that every prime that appears in its prime factorization appears there at least twice. Erdős, Mollin and Walsh conjectured that three consecutive powerful numbers do not exist. This paper shows that if they do exist, the smallest of the three numbers must have remainder 7, 27, or 35 when divided by 36.

Consecutive Prime And Highly Total Prime Labeling In Graphs, Robert Scholle

Rose-Hulman Undergraduate Mathematics Journal

This paper examines the graph-theoretical concepts of consecutive prime labeling and highly total prime labeling. These are variations on prime labeling, introduced by Tout, Dabboucy, and Howalla in 1982. Consecutive prime labeling is defined here for the first time. Consecutive prime labeling requires that the labels of vertices in a graph be relatively prime to the labels of all adjacent vertices as well as all incident edges. We show that all paths, cycles, stars, and complete graphs have a consecutive prime labeling and conjecture that all simple connected graphs have a consecutive prime labeling.

This paper also expands on work …

Combinatorial Identities On Multinomial Coefficients And Graph Theory, Seungho Lee

Rose-Hulman Undergraduate Mathematics Journal

We study combinatorial identities on multinomial coefficients. In particular, we present several new ways to count the connected labeled graphs using multinomial coefficients.

New Experimental Investigations For The 3𝑥+1 Problem: The Binary Projection Of The Collatz Map, Benjamin Bairrington, Aaron Okano

Rose-Hulman Undergraduate Mathematics Journal

The 3x + 1 Problem, or the Collatz Conjecture, was originally developed in the early 1930's. It has remained unsolved for over eighty years. Throughout its history, traditional methods of mathematical problem solving have only succeeded in proving heuristic properties of the mapping. Because the problem has proven to be so difficult to solve, many think it might be undecidable. In this paper we brie y follow the history of the 3x + 1 problem from its creation in the 1930's to the modern day. Its history is tied into the development of the Cosper Algorithm, which maps binary sequences …

Sums Involving The Number Of Distinct Prime Factors Function, Tanay Wakhare

Rose-Hulman Undergraduate Mathematics Journal

We find closed form expressions for finite and infinite sums that are weighted by $\omega(n)$, where $\omega(n)$ is the number of distinct prime factors of $n$. We then derive general convergence criteria for these series. The approach of this paper is to use the theory of symmetric functions to derive identities for the elementary symmetric functions, then apply these identities to arbitrary primes and values of multiplicative functions evaluated at primes. This allows us to reinterpret sums over symmetric polynomials as divisor sums and sums over the natural numbers.

On Orders Of Elliptic Curves Over Finite Fields, Yujin H. Kim, Jackson Bahr, Eric Neyman, Gregory Taylor

Rose-Hulman Undergraduate Mathematics Journal

In this work, we completely characterize by $j$-invariant the number of orders of elliptic curves over all finite fields $F_{p^r}$ using combinatorial arguments and elementary number theory. Whenever possible, we state and prove exactly which orders can be taken on.

Algorithmic Factorization Of Polynomials Over Number Fields, Christian Schulz

Mathematical Sciences Technical Reports (MSTR)

The problem of exact polynomial factorization, in other words expressing a polynomial as a product of irreducible polynomials over some field, has applications in algebraic number theory. Although some algorithms for factorization over algebraic number fields are known, few are taught such general algorithms, as their use is mainly as part of the code of various computer algebra systems. This thesis provides a summary of one such algorithm, which the author has also fully implemented at https://github.com/Whirligig231/number-field-factorization, along with an analysis of the runtime of this algorithm. Let k be the product of the degrees of the adjoined elements used …

Counting Solutions To Discrete Non-Algebraic Equations Modulo Prime Powers, Abigail Mann

Mathematical Sciences Technical Reports (MSTR)

As society becomes more reliant on computers, cryptographic security becomes increasingly important. Current encryption schemes include the ElGamal signature scheme, which depends on the complexity of the discrete logarithm problem. It is thought that the functions that such schemes use have inverses that are computationally intractable. In relation to this, we are interested in counting the solutions to a generalization of the discrete logarithm problem modulo a prime power. This is achieved by interpolating to p-adic functions, and using Hensel's lemma, or other methods in the case of singular lifting, and the Chinese Remainder Theorem.

Statistical Analysis Of Binary Functional Graphs Of The Discrete Logarithm, Mitchell Orzech

Mathematical Sciences Technical Reports (MSTR)

The increased use of cryptography to protect our personal information makes us want to understand the security of cryptosystems. The security of many cryptosystems relies on solving the discrete logarithm, which is thought to be relatively difficult. Therefore, we focus on the statistical analysis of certain properties of the graph of the discrete logarithm. We discovered the expected value and variance of a certain property of the graph and compare the expected value to experimental data. Our finding did not coincide with our intuition of the data following a Gaussian distribution given a large sample size. Thus, we found the …

Deconstructing The Welch Equation Using P-Adic Methods, Abigail Mann, Adelyn Yeoh

Mathematical Sciences Technical Reports (MSTR)

The Welch map x -> g^x-1+c is similar to the discrete exponential map x -> g^x, which is used in many cryptographic applications including the ElGamal signature scheme. This paper analyzes the number of solutions to the Welch equation: g^x-1+c = x (mod p^e) where p is a prime, and looks at other patterns of the equation that could possibly exploited in a similar cryptographic system. Since the equation is modulo p^e, where p is a prime number, p-adic methods of analysis are used in counting the number of solutions modulo p …

Deconstructing The Welch Equation Using P-Adic Methods, Abigail Mann, Adelyn Yeoh

Rose-Hulman Undergraduate Research Publications

The Welch map x -> g^x-1+c is similar to the discrete exponential map x -> g^x, which is used in many cryptographic applications including the ElGamal signature scheme. This paper analyzes the number of solutions to the Welch equation: g^x-1+c = x (mod p^e) where p is a prime, and looks at other patterns of the equation that could possibly exploited in a similar cryptographic system. Since the equation is modulo p^e, where p is a prime number, p-adic methods of analysis are used in counting the number of solutions modulo p …

The Elliptic Curve Discrete Logarithm And Functional Graphs, Christopher J. Evans

Mathematical Sciences Technical Reports (MSTR)

The discrete logarithm problem, and its adaptation to elliptic curves, called the elliptic curve discrete logarithm problem (ECDLP) is an open problem in the field of number theory, and its applications to modern cryptographic algorithms are numerous. This paper focuses on a statistical analysis of a modification to the ECDLP, called the x-ECDLP, where one is only given the xcoordinate of a point, instead of the entire point. Focusing only on elliptic curves whose field of definition is smaller than the number of points, this paper attempts to find a statistical indication of underlying structure (or lack thereof) in the …

Do The Coefficients Of A Modular Form Really "Encode Arithmetic Data"?, Ken Mcmurdy, Hari Ravindran

Mathematical Sciences Technical Reports (MSTR)

Language and terminology are so critical to the understanding of modern math- ematics that it is often difficult for even very good mathematicians from different fields to discuss their work in any detail. As a result, common phrases often evolve within each discipline which attempt to capture the avor of some impor- tant idea while avoiding technicality and jargon. For example, when algebraic number theorists are asked why they are so interested in modular forms, it has become common to say with enthusiasm that the coefficients of a modular form "encode arithmetic data". If pressed further, one might go on …

A Statistical Look At Maps Of The Discrete Logarithm, Nathan Lindle

Mathematical Sciences Technical Reports (MSTR)

Cryptography is being used today more than it ever has in the past. Millions of transactions are being conducted every hour using encrypted channels, most of which use the Internet as their medium. It is taken for granted by the average user that these transaction are secure, but mathematicians and computer scientists alike are constantly testing the algorithms being used. Several of these cryptosystems use the transformation

g^x = y (mod n)

The appeal of this transformation is that it is quite simple to calculate gx mod n; exponentiation by squaring is fairly simple and quick even using …

Mapping The Discrete Logarithm, Daniel R. Cloutier

Mathematical Sciences Technical Reports (MSTR)

The discrete logarithm is a problem that surfaces frequently in the field of cryptog- raphy as a result of using the transformation g^a mod n. This paper focuses on a prime modulus, p, for which it is shown that the basic structure of the functional graph is largely dependent on an interaction between g and p-1. In fact, there are precisely as many different functional graph structures as there are divisors of p-1. This paper extracts two of these structures, permutations and binary functional graphs. Estimates exist for the shape of a random permutation, but …

Pigeon-Holing Monodromy Groups, Niles G. Johnson

Mathematical Sciences Technical Reports (MSTR)

A simple tiling on a sphere can be used to construct a tiling on a d-fold branched cover of the sphere. By lifting a so-called equatorial tiling on the sphere, the lifted tiling is locally kaleidoscopic, yielding an attractive tiling on the surface. This construction is via a correspondence between loops around vertices on the sphere and paths across tiles on the cover. The branched cover and lifted tiling give rise to an associated monodromy group in the symmetric group on d symbols. This monodromy group provides a beautiful connection between the cover and its base space. Our investigation …