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

16
votes
0answers
475 views

Is every model of modular arithmetic either even or odd?

Modular Arithmetic (MA) has the same axioms as first order Peano Axioms (PA) except $\forall x (Sx \ne 0)$ is replaced with $\exists x(Sx = 0)$. ...
7
votes
0answers
58 views

Remainders of Fibonacci numbers

Let $a>b$ be positive integers. Is there a Fibonacci number that is $b$ modulo $a$? We know that the Fibonacci numbers are periodic modulo $a$. Indeed, consider pairs $(F_i,F_{i+1})$ modulo $a$. ...
7
votes
0answers
87 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 ...
5
votes
0answers
79 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
72 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 ( ...
4
votes
0answers
197 views

Prove modular equivalence related to carmichael function.

Statement if $n=p_1p_2p_3\cdots p_r$ (prime numbers are distinct) and $2 \le a \le n-1$ then prove that $$a^{k\lambda} \equiv \left(1+\sum_{p_i\mid\gcd(a,n)}\left(\dfrac{n}{p_i} \right) ...
4
votes
0answers
41 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
109 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
50 views

Calculations in the field $\mathbb{F}_{13}$

The text i am reading claims that $\frac{246}{14}=1$ in the field $\mathbb{F}_{13}$. However, i cannot figure out why this is correct. Since $13 \cdot 18 = 234 \Rightarrow 246 = 12$ and $14 = 1$. How ...
4
votes
0answers
257 views

How to solve congruence $x^y = a \pmod p$?

I'm having trouble solving this congruence: $$x^{114} \equiv 13 \pmod {29}.$$ I thought that it made sense to try to solve it using this idea: "Suppose you want to solve the congruence $ x^y \equiv a ...
4
votes
0answers
74 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 ...
3
votes
0answers
48 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
46 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
78 views

Fibonacci Quadratic Residue

After some research I have came up with a conjecture on fibonacci quadtratic residue: ...
3
votes
0answers
43 views

Modular arithmetic - Suggestions to begin

I've always wanted to start studying modular arithmetic to try to solve problems like: $$\text{find } n \in \mathbb{N} : 4n^2 \equiv 1 ~(\text{mod }{10^4})$$ I have a good basis in mathematical ...
3
votes
0answers
82 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
565 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
87 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
81 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
1k 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
154 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
28 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
20 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 but that doesn't ...
2
votes
0answers
33 views

Size of increments in commutative ring to reach given number

I have the ring $\Bbb Z_q = \{0,1,\ldots,q-1\}$, where $q$ is a prime. Starting from $0$, I want to make exactly $n$ equally sized increments and reach $a\in \Bbb Z_q$, with $n<q-1$. For example if ...
2
votes
0answers
40 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
22 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 ...
2
votes
0answers
37 views

Is there a cycle for modulo operation on a floor?

I have a floor $${\left\lfloor\frac{n}{i}\right\rfloor},$$ where i varies from 1 to n (n can be upto $10^{10}$), and there's another number given 'm' (m upto $10^{5}$). Does ...
2
votes
0answers
47 views

Closed form for the sum $\sum_{a=1}^{b} a^3\cdot (b \bmod a)$

How can we simplify $\sum_{a=1}^{b} a^3\cdot (b \mod a)$? For $a \ge \frac{b+1}{2} $ to $a = b$ it reduces to $$\sum_{a\ge \frac{b+1}{2}}^{b}a^3\cdot (b-a)=b\cdot\sum_{a\ge ...
2
votes
0answers
100 views

“Remainder” operation in mod 2^32

I debated posting this here, in the cryptography SE, or the programming SE. Obviously, I chose here, but I'm not confident in my choice... I'm attempting to "undo" a function, but I've hit a slight ...
2
votes
0answers
36 views

Given any integers $a,b,c$ and any prime $p$ not a divisor of $ab$, prove that $ax^2+by^2\equiv c\pmod{p}$ is always solvable.

The fact that there are $\dfrac{p+1}{2}$ quadratic residues seem to me to help solving the question, but I don't know how to go on from that point. Could you give me any hint?
2
votes
0answers
29 views

System of equations - modular arithmetic

I am asked to solve the following..... Let $n\in \mathbb{N}$ and suppose that $a,b,c,d,k,l\in\mathbb{Z}$. Consider the system $ax + by \equiv k$ mod $n$ and $cx+dy \equiv l$ mod $n$. Let $D=ad-bc$. ...
2
votes
0answers
73 views

Lucas Number Equivalent of the Pisano Period?

I'm doing some work with the Pisano Period, and it's leading to also talk about the Lucas numbers $mod \ m$, and their period. Is there a specific notation already designated? Sticking with using a ...
2
votes
0answers
82 views

Fast check If the remainder is 1

Is there any fast method to 'say' that $R = (A \mod B)$ is $1$ or $R > 1$ or $R \neq1$ or $R > k>1$ ( where $k$ is a small integer on $32$ bits) without to actually calculate the real value ...
2
votes
0answers
39 views

Congruence of polynomials

Prove that $y^i \equiv y^{i \pmod 4} \pmod {y^4 + 1}$ for all $i \ge 0$. Any hints on how to solve this? I don't even know where to start.
2
votes
0answers
161 views

When quadratic formula $ax^2 + bx +c = 0$ (mod p) is solvable modulo prime p?

I am learning about quadratic congruences and I don't now how to decide, for which a,b,c and p there is a solution of the congruence. It is sufficient if the determinant $\sqrt{b^2-4ac}$ has a ...
2
votes
0answers
276 views

How many ring homomorphism are there from $\mathbb{Z} / 12\mathbb{Z}$ to $\mathbb{Z} / 20\mathbb{Z}$? Find the image and kernel of them.

How many ring homomorphism are there from $\mathbb{Z} / 12\mathbb{Z}$ to $\mathbb{Z} / 20\mathbb{Z}$? Find the image and kernel of them. The above is the question, this is my attempt at an ...
2
votes
0answers
59 views

How to find connection between two modulo statements

Given $x\mod n=a$ and $ x\mod m=b$, (here, $n=1000000007$ while $m$ can be any number less than $n$) is there any meathod to find $b$ in terms of $(n,a,m)$...The answer should not contain $x$. I tried ...
2
votes
0answers
35 views

Least value of a multi-residue CRT

Given coprime moduli $m_1,\ldots,m_n$ with $k\ge2$ residues in each modulus, what is the least nonnegative value congruent to one of the specified residues to each modulus? Obviously it must be less ...
2
votes
0answers
36 views

Is there any relation between the modular inverse of the same integer under different modulus?

I mean, suppose $$ab \equiv 1 \mod{m}$$ $$ac \equiv 1 \mod{n}$$ I wonder if there is any relation between $b$ and $c$? Could we compute one from another? Thanks in advance!
2
votes
0answers
36 views

For which minimal $k$ true is that ${4}^{k}\cdot n\leq \displaystyle\sum^{n}_{i=1}{a}_{i}^{k}\leq {5}^{k}\cdot n$, ${a}_{i}\in {1,2,3,4,5,6}$?

I've got the following inequality, which bounds Minkowski distance. ${4}^{k}\cdot n\leq \displaystyle\sum^{n}_{i=1}{a}_{i}^{k}\leq {5}^{k}\cdot n$ and values of ${a}_{i}\in {1,2,3,4,5,6}$ We know all ...
2
votes
0answers
29 views

Name for summation that returns GCD(k,n)

Define $$ H(k,n)=2\sum_{i=1}^{n-1}\left\lfloor\frac{ki}{n}\right\rfloor\;. $$ We can prove that $H(k,n)=nk-k-n+\gcd(k,n)$. Does this $H$ carry some known name?
2
votes
0answers
40 views

eliminate very kth element in mod n… save a given element for last

we are given 1....n numbers. lets say we are to save a given number element k for last in elimination. We start eliminating them in the following manner. I eliminate 1 at first. Then eliminate the ...
2
votes
0answers
67 views

How much information do I gain from each modular inequality?

Problem details: Let $p = 2^{48}$, $s\leftarrow\{0,1\}^{48}$, and $a,b$ known constants. Furthermore let $f(x) = a x + b \pmod{p}$ and let the value $r_k$ be defined by the first-order recurrence ...
2
votes
0answers
121 views

A system of linear equations in integer squares - solvable?

I consider this more a "recreational math" problem, possibly lacking a solution (because it stems from the question of "magic square of squares") or simply intractable with reasonable effort. ...
2
votes
0answers
233 views

Baby-step giant-step algorithm

I have equation in form $a^x = p (\textrm{mod q})$, knowing $p, q, a$. I have to use Shank's algorithm (Baby-step giant-step). I found some exercise and explanation on ...
2
votes
0answers
110 views

Multiplication structure for finite abelian rings of order $p^2$.

Consider an odd prime $p$ and a positive integer $a$ as close to 2 as possible that is not a quadratic residue $mod$ $p$. If we extend the ring $mod$ $p$ with the element $b = a^{\frac{1}{2}}$ then ...
2
votes
0answers
32 views

Solving $key=(\sum_{K=0}^n\frac{1}{a^K})\mod m$ with High limits

I was solving this equation:- $$key=(\sum_{K=0}^n\frac{1}{a^K})\mod m$$ Given $$ 1,000,000,000 < a, n, m \; < 5,000,000,000 $$ $$ a, m \; are \;coprime $$ I solved it bruteforcely but it ...
2
votes
0answers
261 views

$a^{(b^c)} \mod m$ where $c$ can be very very large

I am trying to solve the following problem. I need to find the value of $$ a^{(b^x)} \bmod m $$ where $a,b$ are integers and $$ x = \pmatrix{n\\0}^2 + \pmatrix{n\\1}^2 + ... + \pmatrix{n\\n}^2 ...
2
votes
0answers
119 views

Determining maximum value of $a^b\bmod N$ when $\gcd(a,b)$ is known

Suppose we know the greatest common divisor, $\gcd(A,B)$, of two numbers $A$ and $B$. Is there a way that we can find the maximum value of $a^b \bmod N$ where $N$ is any number? We have a finite ...
1
vote
0answers
21 views

Euler's criterion and Legendre symbol

I am working on an exercise which is the following : Let be $n$ an odd integer and $b$ such as $b \wedge n = 1$, then $(\frac{b}{n}) \equiv b^{(n-1)/2} \mod n$. (*) If $n$ is divisible by the ...