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

Solving for n - modular arithmetic

The question is as follows: So I started by attempting to calculate 12^100 mod 47 by modular exponentiation, which if I'm not mistaken, turned out to be: 12^64 * 12^16 * 12^16 * 12^4 (mod 47) = 37 * 28 * 28 * 9 (mod 47) = 34. So the original…
i.diazr
  • 49
0
votes
0 answers

Extraneous solutions when multiplying out denominators in mods

I was trying to solve a problem where $\frac{n^2(n+1)^2}{4}$ has remainder $17$ when divided by $n+5$. So, I expressed it as $\frac{n^2(n+1)^2}{4} = (n+5) q + 17$. Then, multiplying four on both sides, you get $n^2(n+1)^2 = 4(n+5)q + 68$. Now, I…
abc
  • 23
0
votes
0 answers

Show that a given term is divisible by a given number

Let $k$ be an odd natural number. Show that the sum $\sum_{i=1}^{500} i^k$ is divisible by $501$. This means that: $\sum\limits_{i=1}^{500} i^k \equiv 0 \pmod{501}$ I have researched on the internet for quite some time but don't know how to continue…
Mike M.
  • 29
0
votes
0 answers

If $2^d-1\mid 2^n-1$ then $d\mid n$

It is well-known that if $d,n \in \mathbb{N}^*$ and $d \mid n$ then $2^d -1 \mid 2^n - 1$. Is the reciprocal true ? With a Python program it shows that it may be true (didn't found any counterexample) but I haven't been able to prove it. My attempt…
LexLarn
  • 673
0
votes
1 answer

Solving the following system of equations

Okay, so I have to solve the following system of equations. $$a\equiv 0\hspace{5mm} (\text{mod} \mathbb{Z}/5\mathbb{Z})$$ $$3-a^2\equiv 0\hspace{5mm} (\text{mod} \mathbb{Z}/5\mathbb{Z})$$ For the first equation we have that $a=5n$ for some…
0
votes
0 answers

Finding a number to add for division on both sides in a congruence

If we have to solve for x in $3x ≡ 2 \pmod 5$, then we cannot just immediately divide both sides by 3. Because $\frac{2}3$ is not an integer. Instead, we have to add multiples of 5 to either 3x or 2. In this case, we can add 5 × 2 to 2. $$3x ≡ 2 +…
Hayst
  • 172
0
votes
0 answers

How to solve congruence like these?

So i have three weird congruence that i don't know how to start: $2021^{2021}-2021^{101}≡? \quad (mod \quad 600)$ $46^{47^{48}}≡? \quad (mod \quad 25)$ $39^{1200}≡? \quad (mod \quad 26)$ I know that i have to use euler-fermat formula, but i…
0
votes
1 answer

Solving $x^2 + 7x \equiv 1\pmod{13}$

How should I solve this particular congruence: $x^2 + 7x \equiv 1 \pmod{13}$? I can re-arrange the equation to get $$x^2 + 7x - 1 \equiv_{13} 0$$. In noticing that $7 \equiv_{13} -6$, can I replace $7x$ by $-6x$ in order that the middle term should…
0
votes
0 answers

Modulo operations in a particular set

From Somewhat Practical Fully Homomorphic Encryption section 2.1 "Let $q > 1$ be an integer, then by $\mathbb{Z}_q$ we denote the set of integers $(−q/2, q/2]$. Note that we really simply consider $\mathbb{Z}_q$ to be a set, and as such should not…
0
votes
2 answers

Find x, so that $x \equiv 25! \mod{2001}$

Problem Calculate $x$ so that $x\equiv 25! \mod{2001}$ What I ve tried so far First of all I came up with the correct solution by splitting the problem up into smaller problems, such as: $$25!\equiv [10!]_{2001} \times [11\times 12 \times 13 \times…
T_B
  • 155
0
votes
0 answers

if $ x \equiv y \pmod{4}$ then $n^x \equiv n^y \pmod{10} $

If $x \equiv y \pmod{4}$ then $n^x \equiv n^y \pmod{10} x,y$ and $n$ are intergers. I know that: Since $x \equiv y \pmod{4}$ we have $4|x-y \Rightarrow n^4|n^{x-y}$. $n^x-n^y = n^y( n^{x-y}-1)$
0
votes
1 answer

Finding $a \operatorname{mod} cd$, where $c$ and $d$ are primes

Is there a way to calculate $a \operatorname{mod} cd$, without actually calculating $cd$, where $c$ and $d$ are primes, and $cd$ has $12$ digits?
user91674
0
votes
0 answers

Miller-Rabin test and probabilities

I have to show that if $n = p_1^{a_1}...p_u^{a_u} = 2^dm +1$ is odd and composite (with at least 2 primes dividing n) then the number of integers $k$ such as $1 \leq k \leq n$ and not satisfying the following test : The test is satisfied when one…
badinmaths
  • 456
  • 2
  • 7
0
votes
1 answer

Modulo 2 properties: $(-1)^{(x⊕a)∙y)}=1+(-1)^{a∙y)}$

I am looking at Quantum Physics solution for the Simon's problem. In there there is equation for hadamard gate: I have trouble understanding the step: $(-1)^{(x⊕a)∙y)}=1+(-1)^{a∙y)}$ I was wondering if someone can point to general property of…
0
votes
2 answers

Help with Congruence, How is B Value Calculated

Good afternoon, I am trying to understand congruence, I could really use your help. First time I am using this. I'm working with the congruence formula of ax ≡ b (mod n) I'm following this YouTube explanation of Chinese Remainder Theorem | Sun Tzu's…
KingFish
  • 113
  • 2