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

How to prove $n ≡ n_0 + n_1 + \dots +n_k \pmod{b-1}$

I am trying to prove this statement, where $n$ has base $b$ representation, which can be understood easily using this example: In base $10$, mod $9$ of any number can be found by adding up its digits and doing the mod $9$ of that sum. It's been a…
Bigmario
  • 21
  • 1
2
votes
0 answers

I stumbled across an identity and I don't know to prove it

I stumbled across this apparent identity: $$aa^{-1}_{b}+bb^{-1}_{a}-1=ab$$ where $$ a,b\in \mathbb{N/\{0\}} \\ gcd(a,b)=1 \\ (a^{-1}_{b})\equiv a^{\phi(b)-1} \mod b \\ (b^{-1}_{a})\equiv b^{\phi(a)-1} \mod a \\ $$ Pretty much $a^{-1}_{b}$ and…
2
votes
2 answers

Looking for a better proof in $\mathbb{Z}/11\mathbb{Z}$

We work in $\mathbb{Z}/11\mathbb{Z}$. I want to find the integers $n$ such that the equation $x^n+y^n=0$ has solutions different from $(0,0)$. It's obvious for any odd number $n$. If $n$ is even we can look at what happens only when $x \in…
2
votes
1 answer

Solving ${255\choose 128} \mod 257$

My first thought was to use Wilson's theorem to get rid of the numerator: $$ \dfrac{255!}{128!\cdot 127!} \equiv \dfrac{1}{128!\cdot 127!} \mod 257 $$ But I'm stuck on how to find the inverses of the denominator. If $257$ wasn't prime I could try…
2
votes
1 answer

Arithmetics and Number Theory

Prove that 9 doesn’t divide (2^p)+ 1 always where p is a prime number larger than 5 knowing that this number is divisible by 3
user1178573
2
votes
0 answers

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 some methods but I wasn't able to remove $x$…
aitrom
  • 21
2
votes
1 answer

Remainder of a function in two variables

Supposed a function in two variables is defined as $f(a,b) = \frac{a(a-1)b^{2}}{2}$, and $a,b \in N$ where a is fixed on a certain value while b runs from 1 to n. For instance, $$f(4,1) = \frac{4(4-1)1^{2}}{2} = 6$$ $$f(4,2) = \frac{4(4-1)2^{2}}{2}…
2
votes
2 answers

Modulo operator to short-cut counter-clockwise degrees

I am trying to short-cut the following with modulo, but it is not working for 90 and 270 degrees. What is the correct short-cut? \begin{equation} \delta'= \begin{cases} \delta & \text{if } 0 \le \delta \le 90 \\\\ 180 - \delta &…
a11
  • 123
2
votes
0 answers

Context to "Arithmetic between integers modulo n and integers."

In a recent post I inquired about arithmetic between integers and congruence classes. I learned a lot from the comments and I want to do right by giving a more adequate context to my predicament. I have an equation…
2
votes
1 answer

How to find a mod m when modulus of a mod powers of 2 are given

I need to find the value of a mod m. But I don't have the value of a directly. I have the following modulus values of a. a mod 21 a mod 22 a mod 23 ... a mod 2n Now I need to find a mod m where m < 2n Is it possible to do so with this much…
Shashwat Kumar
  • 322
  • 4
  • 15
2
votes
1 answer

How to compute $a \pmod{m_1}$ given that $a \equiv c \pmod{m_2}$?

Given $m_1, m_2$ and we know that $$a \equiv c \pmod{m_1}$$ Is there a way to directly compute $$a \pmod{m_2}$$
roxrook
  • 12,081
2
votes
2 answers

Show that $x + 1, x^x + 1, x^{x^x} + 1, \dots$ is divisible by $n$

I am doing the pratice in the Junior Problem Seminar by Dr. David A. SANTOS. I came across a question in chapter 2.4 that i had no idea how to do it. This is the question: Shew that for any natural number n, there is another natural number x such…
12 34
  • 37
2
votes
2 answers

Congruence. How would you prove this set equality? (congruence division)

I'd like to prove $$3+4\mathbb Z = \{ x\in \mathbb Z , 3x \equiv 5 [4]\}$$ The $\Rightarrow$ is trivial: $x\in 3+4\mathbb Z \Rightarrow x\equiv3[4] \Rightarrow 3x\equiv5[4]$ But for the reverse way $\Leftarrow$ I get stuck at a certain point:…
niobium
  • 1,177
2
votes
3 answers

For what $n$ do the equations $ab = c, bc = a, ca = b$ have solutions mod $n$?

In $\mathbb Z/(12)$ the elements $5, 7, 11$ have the property that the product of any two of them equals the third: $$5 \times 7 = 11$$ $$7 \times 11 = 5$$ $$11 \times 5 = 7$$ I'm interested in generalizations of this. For what integers $n$ does…
mweiss
  • 23,647
2
votes
1 answer

Find solutions to $(v-u)(v+u-1) \equiv 0 ~ (\text{mod }2(v-1))$

How do we find solutions $(u,v)$ to the congruence $$(v-u)(v+u-1) \equiv 0 ~ (\text{mod }2(v-1))$$? Specifically, we would like to find all solutions with $v$ and $u$ positive integers and $v \geq u$.