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 does this alternative method for determining the remainder when $19^{273}$ is divided by $12$ work?

The question asked: Find the remainder when $19^{273}$ is divided by $12$. My textbook shows an alternative method to complete this question, using modular arithmetic. If we let n be any number, such that: $ 19^{273}$ ≡ $ n^{273}$ (mod 12) $ 19^3…
1
vote
2 answers

How to calculate a missing middle digit of a multiplication between 2 big numbers using modular arithmetic?

What elementary number theory methods can I use for solving this type of questions? One of these kind of problems is to find $x$ where $985242x6565 = 172195\cdot 572167$ without multiplying the numbers again. I tried doing, let's call $985242x6565$…
1
vote
3 answers

Prove by induction for $n\geq1, n \in \mathbb{N}$ $, 2^{2n+1}\equiv 9n^2-3n + 2\pmod{54}$.

Question taken from the book by Andre Weil, titled Introductory number theory, chapter 5, question #V.3. Prove by induction that, if $n$ is a positive integer, then $2^{2n+1}\equiv 9n^2-3n + 2\pmod{54}$. Take base case, $n=1, 2^3\equiv 9-3+…
jiten
  • 4,524
1
vote
1 answer

Simpler modulus operation by splitting number

Someone just shared some code with me that attempts to calculate modulus of big numbers in a more simple way, but I don't quite understand how it works. If you want to know $a$ modulus $b$, where $a$ is some big number, you can split a into digits:…
Luctia
  • 113
1
vote
1 answer

Base 10 theorem in number theory

The question asks: Let $n\ \in \mathbb{N}$ in base $10$ as $n=a_ka_{k-1}\cdots a_1a_0$. Let $m=a_k+a_{k-1}+\cdots + a_1+a_0$. Then $9\mid n$ if and only if $9\mid m$ Here is my Proof: $9\mid n$ implies that $n=9k$ where $k\in \mathbb{Z}$ Next, we…
1
vote
1 answer

Modulus operation with respect to a sequence

Modulus operation with respect to $q\in\mathbb{Z}\setminus{\{0\}}$ (i.e., non-zero integers) is defined as $$a ~\text{mod}~ q = r,$$ where $r$ is such that $a = nq + r$ for some $n\in\mathbb{Z}$ and $r\in\mathbb{N}_0$. Is there a formal definition…
minbraz
  • 11
1
vote
0 answers

Find all $n \in\Bbb N$ such that $2^n -1$ is divisible by $3$ and the congruence $4x^2 \equiv -1\bmod \frac{2^n-1}{3})$ has a solution.

Find all $n \in \Bbb N$ such that $2^n -1$ is divisible by $3$ and the congruence $4x^2 \equiv -1 \bmod\frac{2^n-1}{3})$ has a solution. I haven proven that $n$ must be even in order to satisfy the first equation. On simulating, I found that $n$…
1
vote
5 answers

$63^{63^{63}} \mod 100$

I need to find $63^{63^{63}} \bmod 100$. This is what I've got so far: Since $\gcd(63,100)=1$ we can use Euler's theorem. We have $\phi (100)=40$ so $63^{40} \equiv 1 \mod 100$ Again $\gcd(16,100)=1$ and $\phi (40)=16$, that is $63^{16} \equiv 1…
Noah
  • 159
  • 10
1
vote
2 answers

addition with a variable (mod)

Given $2+x \equiv 7 \pmod 3$. $2 + 0 = 2$ $2 + 1 = 3$ $2 + 2 = 4$ . . . $2 + 5 = 7$ so, the answer will be $x = 5, 8, 11, 14, 17,\dots$ Is this correct? Because somebody told me the answer should be $x = 2, 5, 8, 11, 14, 17,\dots$
MethodManX
  • 1,127
1
vote
4 answers

Modulo question about equality

True or false? $$24 \equiv 77 \mod 16 $$ $1.$ $77/16 = 4.8125 $ $2.$ $4.8125 - 4 = .8125$ $3.$ $0.8125 \times 16 = 13$ $4.$ $24 != 13$ So the answer is false? Am I right?
MethodManX
  • 1,127
1
vote
3 answers

Finding $a \pmod c$ if $a \pmod b$ is known

Suppose that: $Y \pmod B = 0$ $Y \pmod C = X$ I know $B$ and $C$. $Y$ is unknown, it might be an extremely large number, and it does not interest me. The question is: Is it possible to find $X$, and if so, how?
1
vote
2 answers

Modulo question with negative

$60-88 \equiv \,\,? \pmod 5$ $60-88 = -28$ Then what do I do? Please tell me how to answer this question. Thanks.
MethodManX
  • 1,127
1
vote
2 answers

If $R$ is reduced residue system then $\exists! b\in R$ such that $a\equiv b\pmod n$

If $R$ is a reduced residue system modulo $n$ and $\gcd(a,n)=1$ then $\exists! b\in R$ such that $a\equiv b\pmod n$. Recall: $$R=\{a\in C \mid \gcd(a,n)=1\}$$ Where $C$ Is a complete residue system modulo $n$ I didn't quite understand the theorem…
PNT
  • 4,164
1
vote
1 answer

How to solve large modular equations?

I am trying to code a modular equation solver, say given an equation, $x^2=180345$ and the modulo is 8, then we can solve it like this--> $x^2 = 180345 \bmod 8 = 1 \bmod 8$ Now, x can have only the following set of values mod 8: {0, 1, 2, 3, 4, 5,…
Turing101
  • 201
1
vote
2 answers

How to solve for x in modular arithmetic when the equation has exponent?

Say I have the following equation--> $x^2=180345$ and modulo is $8$. I am using an online calculator to solve this equation, and the answer comes out to be $x=1$ or $3$ or $5$ or $7$. I am not getting the maths behind this. It will be very helpful…
Turing101
  • 201