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

Prove that ${ ({ 3299 }^{ 5 }+6) }^{ 18 }\equiv 1\pmod{112}$

How do I solve this? Prove that ${ ({ 3299 }^{ 5 }+6) }^{ 18 }\equiv 1\pmod{112}$ Also, it would be very helpful if you could give me something to read on the topic since this is not taught at my school and this area of mathematics seems…
user329770
5
votes
4 answers

How to find the remainder of $\frac{2^{99}}{9}$?

The question is solved in the book I read in a very odd way as, $$\frac{2^{99}}{9} = \dfrac{{(2^{3})}^{33}}{2^3-(-1)}$$ Hence by remainder theorem the remainder is $-1$. In questions when remainder is negative than the number is subtracted from…
user103816
  • 3,831
5
votes
3 answers

Modulos race, which formula reach 100 first?

I would like to know if there was a way to determine according to this formula: \begin{equation*} \sum_{i=0} \frac{A*i+B \pmod{100}}{100} \end{equation*} and the same with different values of A and B \begin{equation*} \sum_{i=0}…
lopata
  • 319
5
votes
4 answers

Distributive modulo?

I would like to know if the modulo operation has distributivity like this: $$A+B+C \pmod{M} = (A+B)\pmod{M} +C \pmod{M}$$? Does the equality hold true?
lopata
  • 319
5
votes
3 answers

Modular Power equation

I have an interesting problem I solved a while ago, and I was wondering if anyone had a different solution. Let p and q be twin prime integers. Prove that $p^p+q^q\equiv 0 \pmod{p+q}$ I came up with: Proof. First, we are given that we want to…
5
votes
2 answers

How is this a field?

From Stephen Abbott's - understanding analysis there is a section in the text which says: "The finite set $\{0,1,2,3,4\}$ is a field when addition and multiplication are computed modulo 5." I wasn't so familiar with the term "modulo" so quick…
elbarto
  • 3,356
5
votes
4 answers

How to find $x$ if $ x^5 \equiv 7 \pmod {13} $

Solve the following equation: $ x^5 \equiv 7 \pmod {13}$ I think I need to raise both sides of the equation to some power, but I am not sure how to proceed.. Thanks in advance.
Hku
  • 673
  • 5
  • 12
5
votes
1 answer

calculating with residue classes in $\mathbb{Z}{/5\mathbb{Z}}$

How to calculate with residue classes in $\mathbb{Z}{/5\mathbb{Z}}$? $- \overline x \neq \overline x$ but $- \overline x = \overline{5-x}$ $\overline x + \overline y = \overline{x+y}$ $\overline x \cdot \overline y = \overline{x\cdot y}$ So the…
meinzlein
  • 447
5
votes
2 answers

$x^2$ $\equiv$ $1$ $\mod{p}$

Can someone provide the proof that $x^2$ $\equiv$ $1$ $\mod{p}$ iff $x\equiv1 \mod{p}$ or $x\equiv p-1 \mod{p}$, where $p$ is a prime? The argument I have in mind is setting up a bijection, like in the proof Euler's Theorem, and then restricting the…
user82004
4
votes
2 answers

Solving strange Modular arithmetic

I'm trying to solve a form of modular arithmetic I've never seen before. I'm completely stuck. Any hints in how to crack this would be of great help. $$ -18 \equiv 19y \pmod{1967-y}$$ Or similarly, how do I find integer solutions for: $$ y =…
4
votes
5 answers

What is modulo arithmetic

I'm trying to understand what mod means in this equation and how to solve it: d * 13 = 1 mod 1680 This is from how to make a public and private key pair. The answer is 517 apparently and I can get that from wolfram. I assume mod is %, but that…
Brian
  • 141
4
votes
2 answers

Generalization of $n$ mod $2 = \dfrac{1-(-1)^n}{2}$

I had this idea that $n$ mod $2 = \dfrac{1-(-1)^n}{2}$ for $n \in \mathbb{N}$. Are there any generalizations for this? For example for $n$ mod $3$ etc.? I would prefer some answers containing basic arithmetic operations, although the use of…
4
votes
2 answers

How often does a planet with 3 moons have no moon in the sky?

I am designing a planetary system for a role playing game with 3 moons with different orbits. I have created an excel spreadsheet to plan a day in the "current" year where all three moons are in the "new moon" or hidden from the planet stage but I…
Arrya Regan
  • 143
  • 5
4
votes
1 answer

Generalized Euler's totient theorem

We all know that if $a$ and $n$ are coprime, then $a^{\phi(n)} \equiv 1\quad(\text{mod}\ n)$ How can I generalize this to the case where $a$ and $n$ are not coprime? Is the following true? $a^{k+\phi(n)} \equiv a^k\quad(\text{mod}\ n)$ for…
Jasiu
  • 211
4
votes
3 answers

Remainder when $(2023)^{2023}$ is divided by $35$

Finding remainder when $(2023)^{2023}$ is divided by $35$ My Try: We need to find remainder when $(2023)^{2023}$ is divided by $5$ and $7$ So here $2023=0\mod(7)\Longrightarrow (2023)^{2023}=0\mod(7)$ And $\displaystyle…
jacky
  • 5,194