Modular arithmetic (clock arithmetic) is a system of integer arithmetic based on the congruence relation $a \equiv b \pmod{n}$ which means that $n$ divides $b-a$.

learn more… | top users | synonyms

17
votes
0answers
236 views

Finding primes so that $x^p+y^p=z^p$ is unsolvable in the p-adic units

On my number theory exam yesterday, we had the following interesting problem related to Fermat's last theorem: Suppose $p>2$ is a prime. Show that $x^p+y^p=z^p$ has a solution in $\mathbb{Z}_p^{\...
10
votes
0answers
92 views

Is there a clever way to find a smaller number that produces the Euclidean algorithm of given length?

Is there a simple way to tell if for a given $n$ there is $m$ such that the Euclidean algorithm on $n,m$ runs for a given number of steps, and/or a way to find $m$ efficiently (other than testing all $...
10
votes
0answers
201 views

Generalizing the Pell equation $x^2-61y^2 = 1$

In a table of fundamental solutions $f_1(x,y)$ to Pell equations, $$x^2-dy^2=1\tag1$$ with $d<110$, two will stand out, $$(U_{61})^6 = \big(\tfrac{39+5\sqrt{61}}{2}\big)^6 = x+y\sqrt{61} =...
9
votes
0answers
198 views

If $b$ is even and not a power of two, can $b^4+1$ be a weak pseudoprime?

The complete question is already in the title but we shall provide some motivation as well. We study generalized Fermat numbers defined by: $$\mathrm{GF}(n,b) = b^{2^n}+1$$ where $b$ and $n$ are ...
9
votes
0answers
830 views

Decoding Gauss' Easter Algorithm

In 1800, Gauss published this algorithm for computing the date of Easter in a given year $year$: $a = year \mod 19$ $b = year \mod 4$ $c = year \mod 7$ $k = \lfloor year/100 \rfloor$ $p ...
7
votes
0answers
106 views

How to solve $x^x = y^y \mod p$?

Let $p>5$ be a prime. How to solve $x^x = y^y \mod p$? How many solutions are there for a given $p$ such that $x,y < p$? I know the discrete logarithm and the theory of quadratic residues, but ...
6
votes
0answers
83 views

Statement about Woodal primes.

A Woodal number is an integer of the form $n 2^{n}-1$. A Woodal prime is an integer that is both a prime and a Woodal number. Let $p$ be a prime of the form 1 mod 4. Then $p 2^{p} -1$ is never a ( ...
6
votes
0answers
105 views

Composite $n$ such that $\sigma(n) \equiv n+1 \pmod{\phi(n)}$

I'm looking for composite $n$ such that $$\sigma(n)\equiv n+1\pmod{\varphi(n)}$$ Are there only finitely many? Can this be proved? This is Sloane's A070037 but there's not much information in the ...
5
votes
0answers
83 views

Constructing pairs of units $(x,y)$ which solve $x^2 + y^2 \equiv -1 \pmod{N}$

A classic result on the way to the Lagrange Four Squares theorem — for instance proven by Theorem 87 of Hardy & Wright, as noted by this remark on the Four Squares theorem — is that ...
4
votes
0answers
55 views

Why using primes as base in the Rabin-Miller test?

I have done some computer tests with the Rabin-Miller primality test: To test an odd number $n$, write $n=2^r\cdot s + 1$, where $s$ is odd. Given a number $a$ such that $1<a<n-1$, if $...
4
votes
0answers
133 views

Connections between Fibonacci and natural numbers

Here are some known facts about the Fibonacci numbers and then some questions regarding them . 1.Carmichael's theorem : For every $n>12$ $F_n$ has a prime divisor which doesn't divide any of ...
4
votes
0answers
692 views

Find all positive values for j,k,l such that j, k, l are positive integers and (j-k)|l, (k-l)|j, (l-j)|k.

Find all possible values of $j,k,l$ such that $j, k, l$ are positive integers and $(j-k)|l, (k-l)|j, (l-j)|k$. As I understand that using divisibility properties, it is possible to come to some ...
4
votes
0answers
69 views

Exploiting a crypto backdoor based on a polynomial

At a capture-the-flag competition during the weekend, there was a task that involved the following polynomial over the field $F = \mathbb{F}_P$ of integers modulo $P = 571787215471557516425591$ (yes, ...
4
votes
0answers
115 views

Fibonacci Quadratic Residue

After some research I have came up with a conjecture on Fibonacci quadratic residue: $F(x)^2 mod F(y)$ = { if y is even: $(F(|x-y|)^2$ } { if y is odd: $-(F(|x-y|)^2$ } for ...
4
votes
0answers
48 views

Subsets of cyclic group with distinct pairwise differences

Given a number $m\in\mathbb N$, let $\mathbb Z_m=\{0,1,\dots,m-1\}$ denote the ring of integers modulo $m$ (although we won't need multiplication, so any cyclic group of order $m$ will do). Given a ...
4
votes
0answers
203 views

Solving $x^e\equiv a\pmod n$

I am trying to put together the techniques involved in solving $$x^e\equiv a\pmod n, \text{ for known } n\in\mathbb N^*, e\in\mathbb N^*, a\in\mathbb Z_n, \text{ unknown }x\in\mathbb Z_n$$ I'm ...
4
votes
0answers
1k views

How can I solve system of linear equations over finite fields in WolframAlpha?

Is it possible to solve system of linear equations over finite fields using Wolfram Alpha? If yes, how can I do that? Let us take a system $x+y+z=0$, $2x+y+2z=0$, $x+3y+z=0$. If I want to solve this ...
3
votes
0answers
32 views

Recreational math dealing with twin primes

This is kinda recreational math with a goal in mind of progressing further toward a proof of the twin prime conjecture. Consider this: We start with a random prime: $109$ $3*109=327$ $327 \equiv$...
3
votes
0answers
41 views

Quadratic Residues For Odd Modulo

Say I have the formula $$k^2 \equiv b^2 - 4ac \pmod n$$ where are variables are integers and $n$ is odd. So then my question is, if $b^2-4ac$ and $n$ are constant, when is there never a $k$ that will ...
3
votes
0answers
191 views

Finding a minimal perfect hash function for small sets quickly

I'm trying to solve the computer science problem "Minimal perfect hash function" (MPHF). I have an algorithm that can generate a MPHF for very large sets in $O(n)$ that only needs 1.54 bits/key, very ...
3
votes
0answers
96 views

If $\frac{1}{8} \left(5^m-2\cdot 3^m+1\right)$ is prime, then $m=2p$ where $p$ is prime?

The following statements are easy to prove with elementary arguments: $X_m=\frac{1}{8} \left(5^m-2\cdot3^m+1\right)$ is an integer for all integers $m\ge 0$ ($m \equiv 0 \mod 4$ or $m \equiv 1 \...
3
votes
0answers
94 views

Number Theory: Prove that $x^{p-2}+\dots+x^2+x+1\equiv 0\pmod{p}$ has exactly $p-2$ solutions

I just completed this homework problem, but I was wondering if my proof was correct: If $p$ is an odd prime, then prove that the congruence $x^{p-2}+\dots+x^2+x+1\equiv 0\pmod{p}$ has exactly $p-2$ ...
3
votes
0answers
45 views

Prove that for any fixed $n>1$ there exists an infinite amount of such prime $p$, that $p\equiv 1 (n)$

Prove that for any fixed $n>1$ there exists an infinite amount of such prime $p$, that $p\equiv 1 (n)$ Essintially, what's in the title, how do I that?
3
votes
0answers
102 views

Lehmer's totient problem generalization (adding a constant )

Lehmer's totient problem is an well-known open problem which states that the divisibility : $$\phi(n) \mid n-1$$ holds only for primes . This motivated me to ask the following : For which ...
3
votes
0answers
47 views

Is this expression for $x\pmod n$ interesting; nontrivial?

For example, we would get several interesting results if we had a formula for $x\pmod n$ that was uniformly convergent, however, according to Wikipedia (Floor and Ceiling Functions) these formulas do ...
3
votes
0answers
77 views

System of linear congruence, not relatively prime

Consider we have the following set of congruences $$x\equiv b_i \pmod {m_i}$$ for all $1\leq i\leq d$. $m_i$'s doesn't have to be relatively prime, so the Chinese remainder theorem doesn't work here. ...
3
votes
0answers
52 views

Finite strings of integers from $\{1,1,2,2,\ldots,n,n\}$ such that there are $k$ elements between the two $k$s

A friend was recently posed with the following interview questions. Write a string of six elements containing two $1$s, two $2$s, and two $3$s such that between the two appearances of the '$k$' ...
3
votes
0answers
71 views

Simplify this number using modular arithmetic.

Find the last 10 digits of the number $9511627776^{195761}2^{17}$. Well, I know I just have to perform $$9511627776^{195761}2^{17} \mod 10^{10}$$ and I know that $195761$ is prime. Also, $9511627776 ...
3
votes
0answers
188 views

Modular nth roots, e.g. $x^5 \equiv 6 \pmod{31}$

I want to algorithmically solve the (large integer) modular root equation $$x^n \equiv a \pmod {p^k},$$ assuming for simplicity that $p$ is prime, $\gcd(a,p)=1\;$ and $n$ odd. If $q \equiv n^{-1} \...
3
votes
0answers
56 views

Combinatorial interpretation of an equality

In a recent project, I came up with the following equality which turned out to be extremely useful for counting conjugacy classes in certain division algebras (I won't go into the details here, it's ...
3
votes
0answers
55 views

Strange things on WolframAlpha: derivation, modulo and doubling result

I asked WA what is the derivative of $\frac1{\cos((x \bmod \pi/2)-\pi/4))}$ equal to for $x=0$. A very strange result came out. The exact result is $-\sqrt2 \mathsf{Mod}^{(1,0)}(0,\frac\pi2)$, ...
3
votes
0answers
88 views

Find n's for which $P_n$ is prime.

Consider the numbers $P_n=(3^n-1)/2$. Find $n$'s for which $P_n$ is prime. Conjecture: If $n \equiv 1 \mod 6$, and $n$ is prime, then $P_n$ is prime. I have tried proving this by contradiction but ...
3
votes
0answers
93 views

Equivalence classes of triplets satisfying $x^2+y^2+z^2=0$ over $\mathbb{F}_p$

The affirmative answer to this question illustrates that the equation $$x^2+y^2+z^2=0$$ has $p^2-1$ nontrivial solutions over $\mathbb{F}_p$ (solutions that are not $(0,0,0)$). If $(x,y,z)$ is a ...
3
votes
0answers
96 views

An intuitive interpretation of Montgomery pair corrlation function vs. prime divisibility?

Theorem - If the Riemann hypothesis would be true, and the Montgomery pair correlation conjecture (see linked article page 183-184) true too; let $p \in \Bbb P$ prime, $n \in \Bbb N$ and $$\mathcal ...
3
votes
0answers
2k views

Curious 123456789 x 8 + 9 = 987654321

I was recently asked why the following results holds \begin{align} 1 \times 8 + 1 &= 9 \\ 12 \times 8 + 2 & = 98 \\ 123 \times 8 + 3 & = 987 \\ 1234 \times 8 + 4 & = 9876 \\ 12345 \...
3
votes
0answers
170 views

Number of elements in projective special linear group over $\mathbb{Z}/n\mathbb{Z}$

While reading a paper about the modular group $\Gamma = PSL_2(\mathbb{Z})$, I came upon the following sentence ($\Gamma(N)$ is the kernel of the canonical map $PSL_2(\mathbb{Z}) \rightarrow PSL_2(\...
2
votes
0answers
15 views

Solving Modular Equation

Let $d$ and $n$ be coprime. What is the smallest positive solution for x in the equation: $$d^x \equiv 1 \mod n$$ This value must depend on both $d$ and $n$. We know that the maximum value for it is ...
2
votes
0answers
39 views

Proof of the Ribet's theorem

My question is very simple : My goal is to read a proof the proof of the epsilon conjecture proven by Ken Ribet (1986) which is an ingredient of the proof of the Fermat Last Theorem (I want the ...
2
votes
0answers
51 views

Finding solutions in modulo

If I know $x$ modulo m and n, then under what conditions on m,n and p will i necessarily know $x$ modulo p? My initial guess is only in trivial cases, i.e. p is a multiple of m or n, but i cant seem ...
2
votes
0answers
35 views

Pattern involving squares, primes, and remainders

I ran across a really neat pattern, wholly by accident. In advance, my questions are: Has this been discovered before? If so, where can I learn more about it? Why does this pattern work? Now for ...
2
votes
0answers
29 views

Division in modular arithmetic

Let $p$ be an odd prime. Given that $a\equiv b \pmod p$ and $c \equiv d \pmod p$, such that none of $a,b,c,d$ is a multiple of $p$. Under what conditions, $\frac{a}{c} \equiv \frac{b}{d} \pmod p$.
2
votes
0answers
20 views

Mathematical development with Polynom modulo n

I have to implement a method seen in an article, and I'm stuck with some mathematical development. The article is on iEEE Xplore, so I'll try to be as specific as I can. It's about pairing-based ...
2
votes
0answers
27 views

A problem in modular arithmetic.

Given large $n\in\Bbb N$ is there many $a,b\in(n,2n)$ with $\gcd(a,b)=1$ and $q,r\in(n^4,2n^4)$ with $\gcd(a,bq)=\gcd(ar,b)=1$ and $c,d\in(n^3,2n^3)$ with $-n<-x=q\bmod c,-y=r\bmod d<0$ with $\...
2
votes
0answers
125 views

A property on finite sequences $1,1,x_2, x_3, \dots, x_{n-1}$ with $x_i \in \{0,1\}$

Consider a finite sequence $$x_0, x_1, \dots, x_{n-1}$$ with $n$ odd, all $x_i \in \{0,1\}$ and in particular $x_0 = x_1 = 1$. Furthermore, assume that the number of nonzero $x_i$ is even and $\leq (n+...
2
votes
0answers
44 views

simplifying a sum with modular arithmetic

Let $p\!\geq\!3$ be a prime and $n\!\in\!\mathbb{N}$. For $i\!=\!1,\ldots,n$ let $w_i\!=\!2i\!-\!n\!-\!1$. Let $n\%p$ denote the remainder in the integer division of $n$ by $p$. Can the following sum ...
2
votes
0answers
29 views

Generating function for the Josephus Problem?

According to the Wikpedia article on the Josephus problem, the general solution is by dynamic programming. However, since there seems to be an explicit recurrence rule for the problem, should there ...
2
votes
0answers
144 views

Find polynomial congruent to function modulo 6

How to find polynomial with rational coefficients, which is congruent to given function (or prove that it doesn't exist)? Particularly, how to find $P(x)$, so $$P(x)\equiv 4\left\lfloor\frac{x}{6}\...
2
votes
0answers
21 views

Reformulating diophantine inequalities

Assume we are given inequalities $x \not\equiv a_i\text { (mod }b_i)$ for $i=1,\ldots,n$ where $1 \leq a_i \leq b_i, x \in \mathbb{Z}$. Can we somehow reformulate the problem as $x \not\equiv a_i'\...
2
votes
0answers
77 views

Show that the equation $x^2+y^2+z^2= (x-y)(y-z)(z-x)$ has infinitely many solutions in integers $x, y, z$.

Show that the equation $x^2+y^2+z^2= (x-y)(y-z)(z-x)$ has in finitely many solutions in integers $x, y, z$. It seems like if I find a set of $x,y,z$ that satisfy this for any values that will prove ...
2
votes
0answers
50 views

If $a^n+n^b\mid c^n+n^d$ for every $n$ then $c=a^k$ and $d=kb$ .

I made a generalization of the following problem (it's a problem from the IMO shortlist in some year) : Let $a,b$ be fixed positive integers . If : $$a^n+n \mid b^n+n$$ for every positive integer $...