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

26
votes
0answers
341 views

Fractals using just modulo operation

Let us calculate the remainder after division of $27$ by $10$. $27 \equiv 7 \pmod{10}$ We have $7$. So let's calculate the remainder after divison of $27$ by $7$. $ 27 \equiv 6 \pmod{7}$ Ok, so ...
10
votes
0answers
173 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} ...
8
votes
0answers
584 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
91 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
81 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
91 views

Number Theory: $x^2\equiv 1\pmod{140}$

I have this problem assigned for homework and I'm confused as to how to solve an $x^2$ congruence. Here is the problem: $x^2\equiv 1\pmod{140}$ My only thought was to do something along the lines ...
5
votes
0answers
81 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 ...
5
votes
0answers
85 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 ...
4
votes
0answers
112 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
361 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
65 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
109 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
47 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
173 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 ...
3
votes
0answers
32 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
19 views

Probability of two correlated numbers modulo p being part of a subset

Let $p$ be a prime number and $x$ be a number chosen uniformly at random from $0,...,p-1$ and let $y=cx \mod p$, where $c$ is some integer in $1,...,p-1$. Let's suppose we chose at random $p/2$ ...
3
votes
0answers
77 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
59 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
100 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
46 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
51 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
50 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
69 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
55 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
54 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
86 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
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
92 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
168 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
68 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
52 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
151 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 ...
2
votes
0answers
66 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
43 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
38 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
26 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
52 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
40 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: ...
2
votes
0answers
20 views

A stochastic variant of the heat equation modulo $2\pi$ has weird unstable particle-antiparticle solutions. Does this equation have a name?

I implemented a discretization of a weird 2D heat equation "mod $2\pi$", $$\dot{f}(\mathbf{x},t)=\Delta^*f(\mathbf{x},t)$$ where (WARNING: handwavy, I'm not sure I understand it) ...
2
votes
0answers
43 views

Is the multiplication modulo $p$ for polynomials well-defined?

Is the multiplication modulo $p$ for polynomials well-defined ? I mean let $g,h\in\mathbb Z[x]$ and let $\bar g$ be the polynomial obtained from $g$ by reducing all the coefficients of $g$ modulo ...
2
votes
0answers
91 views

Are there Latin squares with no repeats on the diagonal not of the form 2y+x+1(mod n)?

I am looking for a certain kind of latin square (nxn). Rules: No repeats in any column or row (Definition of Latin Square) No repeats in any diagonal including others than the main diagonal. So ...
2
votes
0answers
286 views

Fastest way to find modular multiplicative inverse

I am looking for a fast way to find the modular multiplicate inverse of an integer $a$ in mod $p$. I am mainly interested in ...
2
votes
0answers
40 views

Which primes satisfy this modular property?

Let $x$ be a residue$\mod p$ where $p$ is an odd prime. Im searching for such $p$ such that there exists a function $f(x)$ with propery $f(f(x)) - 2^x \equiv 0 \mod p $ for all values of $x$. I ...
2
votes
0answers
52 views

How to simplify expression with Fermat's little theorem

I don't quite understand how to reduce $(25^{74} + 53^{27})^{10}$ I thought I would reduce to $(4^{74} + 4^{27})^{10}$ and then $(4^{7*10 + 4} + 4^ {7*3 + 6})^{7*1 + 3}$ And then $(4^4 + 4^6)^3$ ...
2
votes
0answers
53 views

Compute digits of a number.

The question is what the last $10$ decimal digits of $2^{3^{4^{5^{6^{7^{8^9}}}}}}$ are? I do not get the following solution and its motivation. I would appreciate if someone would shed light on it. ...
2
votes
0answers
47 views

Divisibility in different Modulo.

So I've actually been working with congruences recently in class and most of the time I end up using Fermat or the Euler Totient function to simplify a large exponent. In general, I run into a ...