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

10
votes
0answers
87 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
192 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
196 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
807 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
103 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 ( ...
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
131 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
557 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
68 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
114 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
193 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
31 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 ...
3
votes
0answers
39 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
181 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
94 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
89 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
43 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
70 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
179 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
94 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 ...
2
votes
0answers
19 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
117 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 ...
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
87 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 ...
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 ...
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 ...
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 ...
2
votes
0answers
73 views

Solve the congruence relations for x

I have the following two congruence relations: (1) $x^3\equiv 156417\pmod {262063}$ (2) $(7x+19)^3\equiv 6125\pmod {262063}$ And I need to solve this for x. I changed equation (2) into the ...
2
votes
0answers
60 views

Solve the congruence system

I'm asked to solve the following congruence system: $$ \begin{split} x &\equiv 2 \pmod{5}\\ 2x &\equiv 1 \pmod{7}\\ 3x + y &\equiv 4 \pmod{11} \end{split} $$ But I think that by ...
2
votes
0answers
69 views

Solving a modular equation

For a given $k \geq 0$, following identity holds for all positive integers $a$. How can I find $n$? $$a^{n+k} \equiv a \mod n$$ Examples: If $k=0$, then solution of $n$ is the set of all primes. If ...
2
votes
0answers
52 views

If n>6 is an even perfect number, Prove that n is congruent to 4 (mod12)

I know that for n to be an even perfect number greater than 6 it has the form $ 2^(m-1)(2^m-1)$ where m is prime. I also know that since n is an even perfect number, it is congruent to 1 (mod 9). ...
2
votes
0answers
39 views

Squares of $F_{467}$ and 7 as a quadratic residue of a prime mod that prime

I am having a hard time understanding what exactly is meant by this question. Could someone give me a solution with a clear explanation? If $x=467$, are 111 127 and 225 squares in $F_x$? Explain your ...
2
votes
0answers
30 views

How can I show that $x \equiv b^{u} \pmod m$ is always a solution to $x^{k} \equiv \pmod m$, even if $\gcd(b,m) \gt 1$?

How can I show that $x \equiv b^{u} \pmod m$ is always a solution to $x^{k} \equiv \pmod m$, even if $\gcd(b,m) \gt 1$? Our method for solving something like $x^k \equiv b\pmod m$ is first to ...
2
votes
0answers
40 views

$a$ and $n$ are relatively prime then there exists an integer $k$ such that $ak \equiv 1(\mod n) $.

Let $n \in Z$, $n > 1$ and let $a \in Z$ with $1 \leq a \leq n$. Prove that if $a$ and $n$ are relatively prime then there exists an integer $k$ such that $ak \equiv 1(\mod n) $. Proof: Suppose ...
2
votes
0answers
58 views

Generalized modulo arithmetic

This question (and especially this answer and the comments on it) actually made me think about a sort of generalized modulo arithmetic that would deal with all modulos at once and would basically make ...
2
votes
0answers
41 views

How do I interpret “K2 mod K1”?

I've been doing a bit of work these past couple of nights on computing cyclic subspace decompositions, finding cyclic bases, and then computing the Jordan canonical form of matrices. My question is: ...