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
2
votes
2 answers

Why is $x^7 = x$ true for every $x$ in $x ∈ Z/14Z$?

I'm trying to solve $x^7 = x$ in $x ∈ Z/14Z$. I tried it in Wolfram Alpha and I know it's true for every $x$ but I don't know why. Any help appreciated.
2
votes
2 answers

Modular numbers

I just learned about modular numbers on wikipedia, such as $17 \equiv 3\pmod{7}$. So what is infinity $\pmod{n}$? It can't very well be all the numbers at once, so what happens?
Chris Brooks
  • 7,424
2
votes
2 answers

Generic Question Regarding modular arithmetic

I was going over a paper regarding linear algebra and its relation to chaos. One particular section focuses on Arnold's cat map. It briefly mention modular arithmetic. In this case, it dealt with the generic form of $x \hspace{1mm} mod…
Mlagma
  • 1,677
2
votes
1 answer

Finding cubic and quintic residues $\mod31$ quickly

I am trying to solve $a^3+b^5 = 7^{7^{7^7}}$. I have proven that $7^{7^{7^7}} \equiv 19\mod31$ using Fermat-Euler Theorem. A previous answer on this site asserts that $19$ is not equivalent to the sum of a cube and fifth power $\mod31$. Is there a…
2
votes
4 answers

Prove with modular arithmetics that $4^n =4 \pmod 6$.

How do I prove $4^n\equiv 4\pmod 6$ where $n \in \Bbb Z_+$? I was always doing it by checking $n \in \{1,2,3,4,5 \}$ and if there was a pattern then I assume that it is correct. So I was wondering if there is a easier and faster way to prove it with…
VereX
  • 181
2
votes
2 answers

Solving linear equation modulo two pi

I have an equation I'd like to solve given as $$s \cdot \alpha \equiv p (\mathrm{mod} 2 \pi) $$ The numbers $s$ and $p$ are known, while $\alpha$ is to be solved for, and additionally is between $0$ and $2 \pi$. I have found a solution using other…
Noah D
  • 23
2
votes
0 answers

Containment within an Interval

A friend of mine asked me to write a function which, given a time of day and a interval of times, determines whether the first time is within the range accounted for by the second. For the purposes of this discussion, let's simplify his problem and…
2
votes
2 answers

How can I calculate $24^{33} \bmod 80$

How can I calculate $24^{33} \mod 80$. I don't see how to start. I only know that $\phi (80) = 32$. A hint would suffice, thanks!
simp
  • 883
2
votes
2 answers

Basic doubt in Fermat's Little Theorem

The minimum positive integer p such that 3^p modulo 17 = 1 is a. 5 b. 8 c. 12 d. 16 I got the answer as 16 by applying Fermat's Little theorem. But does this theorem makes sure that is the min. value?I mean is it possible to have number less than…
2
votes
0 answers

What does "modulo $n$" mean in this context?

Let $a,b,c,d\in\mathbb{Z}/n\mathbb{Z}$ and $$f(a,b,c)=\exp\left(\frac{2\pi x i}{n^2}a(b+c-[b+c])\right).$$ Here $x\in\{0,...,n-1\}$ and $[b+c]=b+c\mod n$. Now, it is given that the following…
2
votes
0 answers

Calculate the sum of following series

Given: Two co-prime natural nos $a,b$ Find: $$S=\sum_{i=1}^n\left((ib)\bmod{a}\right)$$ i.e $$S=(b\bmod{a})+(2b\bmod{a})+(3b\bmod{a})+...+(nb\bmod{a})$$ My approach: This is periodic with length of $a$. If $n$ is a multiple of $a$, then all…
maverick
  • 1,319
2
votes
4 answers

Find the last digit of $43^{43^{43}}$

Find the last digit of $43^{43^{43}}$. My attempt: $$(40+3)^3 \equiv 3\cdot 40\cdot 9+27 \equiv 1080+27\equiv 07\pmod{100}$$ Am I right or is there any other way to find the answer?
2
votes
2 answers

modular multiplicative inverse

I have a homework problem that I've attempted for days in vain... It's asking me to find an $n$ so that there is exactly one element of the complete residue system $\pmod n$ that is its own inverse apart from $1$ and $n-1$. It also asks me to…
hello.world
  • 127
  • 4
2
votes
0 answers

Square roots of $2$ in $\mathbb{Z}_{119}$.

How can I find all the square roots of $2$ in $\mathbb{Z}_{119}$. I understand that I have to solve the equation $[x]^{2} = [2]$ in $\mathbb{Z}_{119}$, but I am not sure how to proceed.
u123435
  • 173
  • 1
  • 5
2
votes
3 answers

checking of understanding solution of linear congruent equation

Let us consider following equation $${30x}\equiv 24\pmod {72}.$$ I would like to understand steps of solving such equation, first of all let us find GCD of two number $30$ and $72$ $$d=gcd(30,72)=6. $$ after that we can write like…