Questions tagged [modular-arithmetic]

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 $a-b$.

Modular arithmetic (clock arithmetic) is a system of arithmetic of integers. The basic ingredient is the congruence relation $a \equiv b \bmod n$ which means that $n$ divides $a-b$. In modular arithmetic, one can add, subtract, multiply, and exponentiate but not divide in general. The Euclidean Algorithm, the Chinese Remainder Theorem, and Fermat's Little Theorem are important throughout mathematics. Modular exponentiation plays an important role in cryptography nowadays.

11320 questions
1
vote
0 answers

Why 'congruent with 1' implies the period in a modular exponentiation sequence?

This question is related to Shor's algorithm (for quantum computing) and its use of modular exponentiation. In the table below, the period of the third column is obviously equal to 4. That is, its value repeats every fourth row. What I am trying to…
1
vote
2 answers

What kind of curve does $f(x)=c\pmod x$ produce?

Using the modulus operation on a constant over a continuous set of real numbers produces what at first appears to be an orderly, linear graph when zoomed out. However, when zooming in, the plot quickly becomes chaotic, with changes in direction that…
1
vote
2 answers

Show $2\mid (n^7 -n), \forall n \in\mathbb{N}$.

Show $2\mid (n^7 -n), \forall n \in\mathbb{N}$. $n^7 \equiv n \bmod 2\implies n^6 \equiv 1 \bmod 2$ Using Fermat's little theorem, it is easy to see that: $n^1 \equiv 1\bmod 2\implies n^a \equiv 1^a\bmod 2, \forall a \in \mathbb{N}$ Algebraic…
jiten
  • 4,524
1
vote
6 answers

Is it possible to calculate $3^{-1}\equiv ?\pmod{10}$?

If I wanted to calculate $3^{-1}\equiv ?\pmod{10}$ would I first calcuate $3^1$ which is just $3\equiv 3\pmod{10}$ and then divide both sides by $3^2$ which would get $3^{-1}\equiv 3^{-1} mod{10}$ Then im not sure what to do next. My book states…
user60887
  • 2,935
1
vote
0 answers

Modular arithmetic formula for months where $m$ mod 12 outputs 12 instead of 0?

I'm working on a project where we're performing monthly date arithmetic: adding $n$ months to an initial month $m_1$ to obtain a resulting value of 1 through 12. The standard modulo operation, $m_2$ = ($m_1 + n$) mod 12, will return the remainder…
RobertF
  • 197
1
vote
1 answer

Heegner Number Modular Arithmetic

Why are all Heegner numbers > 8 (up to 163) all equal 3, mod8 i.e Let $H$ denote a Heegner number. When $H$ > 8 $$H \equiv 3\mod8$$
1
vote
0 answers

Solving Base of Modular Exponential Arithmetic

I am fairly new to modular exponential arithmetic and I came across the discrete logarithm problem which, for equation $$c = a^b mod(n)$$ it is extremely hard to solve for b, when we know the values for c, a and n. My question is, does this same…
Jimmy
  • 11
1
vote
0 answers

Find ones digit of $1^1+2^2+3^3+\cdots+117^{117}$

Find the ones digit of $$1^1+2^2+3^3+\cdots+117^{117}$$ My work: The problem is equivalent as finding $1^1+2^2+3^3+\cdots+117^{117}$ modulo 10. I tried Euler's theorem, finding $$a^4\equiv 1 \text{ (mod 10)}$$ However, the problem is that it only…
Cyh1368
  • 839
1
vote
0 answers

Proof involving sets and reflexive tuples under modulo

Intro: Recently, in a Deep Learning class, I was asked to prove that circulant matrices are commutative under matrix multiplication (you may see where my problem comes from with this information). There was one part of my original approach to this…
1
vote
1 answer

How to solve an exponential congruence equation

The question is rather simple, but I spent the entire afternoon googling and found no help in order to solve such questions: $$2^x \equiv 16 \pmod{127}$$ What are the general steps to solve such questions? I've tried looking for some materials, but…
1
vote
1 answer

Chinese Remainder Theorem with unknown moduli

We are counting intervals of prime width that can be covered by a set of primes. (By covered we mean every element is a multiple of one of primes.) Formally, Let $p_1, \dots p_n$ be the first $n$ prime numbers and $A=(m_1, \dots, m_{p_{n+1}-1})$ be…
1
vote
4 answers

Can modulo be used in consecutive multiplications or divisions?

I used to participate in programming competitions and at times I see that the solution should be the remainder when divided with some big prime number (usually that would be 1000000007). In one of the problems, I need to divide a very big number by…
1
vote
1 answer

Solving linear congruence after Extended Euclidean algorithm

I am attempting to solve $ 769x\equiv1066 \mod 2022 $ Using the Euclidean Algorithm I have found the following: $ 823\cdot 769 - 313\cdot2022 = 1 $ I am attempting to represent the solution in the form $ x\equiv a\mod n $ where $ 0 \le a\le n…
Ben
  • 278
1
vote
0 answers

I have been calculating Modular arithmetic for 2 by 10 but I don't understand what happened

So I have been calculating $2^{n}$ by $10$ until I find $n$ where n is a natural number. Basically, I have trying values of $n$ from $0$ onward until I find the number where it keeps repeating. But here is the thing: $2^{0} \equiv 1 \pmod…
1
vote
1 answer

if a+b+c+d=5m, what are the sets of values of a,b,c,d for which 5 divides none of them?

Let's assume $a+b+c+d$ is an integer multiple of $5$, that is $$a+b+c+d=5m-------(1)$$ For all integer $m,$ where $5$ does not divide any of $a,b,c$ and $d$. What are all the sets of values of $a,b,c,d$? The sets I could find are: $$5w+1, 5x+1,…