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

15
votes
0answers
420 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)$. ...
6
votes
0answers
51 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
70 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
154 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
32 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
95 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
49 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
225 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
72 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
44 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
67 views

Fibonacci Quadratic Residue

After some research I have came up with a conjecture on fibonacci quadtratic residue: ...
3
votes
0answers
40 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
77 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
63 views

Find all $x,y\in\mathbb{Z}$ s.t $2x^3-7y^3=3$

Find all $$x,y\in\mathbb{Z}$$ such that $$2x^3-7y^3=3$$ Solution: We consider first $$2x^3-7y^3\equiv3 \pmod 2$$ $$5y^3\equiv 1 \pmod 2$$ $$y^3\equiv 1 \pmod2$$ which has solution $y\equiv 1 ...
3
votes
0answers
459 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
73 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
936 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
151 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
92 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
30 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
22 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
69 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
81 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
59 views

Find all integers n which satisfies $1^n+9^n+10^n=5^n+6^n+11^n$

Find all $n\in\mathbb Z$ which satisfies $1^n+9^n+10^n=5^n+6^n+11^n$ for $n=2\ or\ n=4$ it is equal but are there other numbers?
2
votes
0answers
32 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
131 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
57 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
31 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
66 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
120 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
202 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
109 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
199 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
115 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
11 views

Constructing a periodic piecewise (piecemeal) function in Maple.

I'm trying to make a piecewise function that will have period $12$. That is, it repeats every $12$ units across the $x$-axis. I managed to do one cycle successfully with ...
1
vote
0answers
22 views

In $Z[x]$, which pairs of $a,b$ commute as modulo operators, such that ($c$ mod $a$) mod $b =$ ($c$ mod $b$) mod $a$ for every $c$?

In $Z[x]$, which pairs of $a,b$ commute as modulo operators, such that ($c$ mod $a$) mod $b =$ ($c$ mod $b$) mod $a$ for every $c$? What I got so far is: Clearly the equasion holds for every pair ...
1
vote
0answers
41 views

Given $m^2\bmod A$ and $m^2\bmod B$, how do you find $m^2 \bmod AB$?

Given $m^2\bmod A$ and $m^2\bmod B$, how do you find $m^2 \bmod AB$? I'm 99% sure this is an application of the Chinese remainder theorem, although my workings do not quite show how it can be ...
1
vote
0answers
25 views

generalized expression required

suppose i have a set $ {0,1,2.......x-1}$ Now I am generating an i length sequence using the numbers from above set...${a0,a1,....ai}$ where all $ai$$>=0 $ and $ai<=x-1$ Note numbers may ...
1
vote
0answers
13 views

Jacobi Form and its Fourier expansion

Let k,m be non negative integers. A Jacobi form of weight k and index m is a holomorphic function f on $\mathbb{H} x \mathbb{C}$ (where $\mathbb{H}$ denotes the upper half plane) satisfying the ...
1
vote
0answers
27 views

Floor function inequality: $\frac{n^2}{x}-\left\lfloor\frac{n^2}{x}\right\rfloor+\frac{2n+1}{x}-\left\lfloor\frac{2n+1}{x}\right\rfloor<1$

I would like to dissect the following inequality to figure out its properties. $$\frac{n^2}{x}-\left\lfloor\frac{n^2}{x}\right\rfloor+\frac{2n+1}{x}-\left\lfloor\frac{2n+1}{x}\right\rfloor>1$$ ...
1
vote
0answers
31 views

solving congruence equation system modulo prime

I need to solve a congruence system like this: $30f_0+26f_1+8f_2+38f_3+2f_4+40f_5+20f_6 \equiv 0 \pmod{41}$ $38f_0+2f_1+40f_2+20f_3+30f_4+26f_5+8f_6 \equiv 0 \pmod{41}$ ...
1
vote
0answers
27 views

Help for solving quadratic residue.

I am solving CRYPTO1 problem. This problem requires to solve following equation: $$x^2=q(\mod p)$$ where I am given $p=4,000,000,007$ and q is also given. I followed ...
1
vote
0answers
66 views

Solving the discrete logarithm using index calculus, finite fields and factor bases.

(a) Let $p$ be the prime 1073741827, with $\Bbb{F}_p$ the corresponding finite field. A primitive root in $\Bbb{F}_p$ is equal to $g=2$. Use a factor base of primes up to 13 to find the discrete ...