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
1 answer

Fastest approach for solving a modulo equation

i should solve $a\cdot 57 \equiv_{39} 1$ for $a\in \mathbb Z$ My first idea was: $a\cdot 57 \equiv_{39} 1 \ \ \Leftrightarrow \ \ 39 | (a\cdot 57 - 1 ) \ \ \Rightarrow \ \ a\cdot57-1=n\cdot 39\ \ \forall n \in \mathbb N \setminus \{0\}$ so we get:…
xotix
  • 887
0
votes
1 answer

Show that for all odd integers: $a^{2^n} \equiv 1 \pmod {2^{n+2}}$

Show that : $a^{2^n} \equiv 1 \pmod {2^{n+2}}$ for all odd integers. The question states to show that all odd integers satisfy the 3 congruence: 1. $a^4 \equiv 1 \pmod{16}$ 2. $a^8 \equiv 1 \pmod{32}$ 3. $a^{16} \equiv 1 \pmod{64}$ and then…
jiten
  • 4,524
0
votes
2 answers

Divisibility rules based on modulo arithmetic.

In Uspensky's text 'Elementary Number Theory' on pg. 131 there are 3 rules given for division by $9, 3, 11$. I am detailing below, with the exercise part for the same for $7$: Let a number $N$ be represented in the decimal notation as : $$N = a +…
jiten
  • 4,524
0
votes
1 answer

Find $X^2 \equiv 9 \pmod {13}$ without consulting table?

Find $X^2 \equiv 9 \pmod {13}$ without consulting table? The answer is given as $3, 10$, but without consulting tables it would mean : $X^2 - 9 \equiv 0 \pmod {13}$ So, either $(X-3)$ or $(X+3) $ is divisible by $13$, as difference between the…
jiten
  • 4,524
0
votes
0 answers

Please vet modulo question: $77546 + x - 465 = 513* 663 \pmod{92}$.

I am doing simple question on congruence modulo arithmetic, and my attempt is: $77546 + x - 465 = 513* 663 \pmod{92}$ => $77081 + x = (460+53)*(644+19) \pmod{92}$ => $ (92000-14919) + x = (53)*(19) \pmod{92}$ => $ (92000-(9200+5719)) + x =…
jiten
  • 4,524
0
votes
0 answers

Does increasing the modulo decrease collisions?

For example, ISBN 10 uses its 10th digit as the check digit. It's the value that when added to all other digits multiplied by some weight must be divisible by 11. $(10x_{1}+9x_{2}+8x_{3}+7x_{4}+6x_{5}+5x_{6}+4x_{7}+3x_{8}+2x_{9}+x_{{10}})\mod…
0
votes
4 answers

Modular algebra with an non-integer solution

Suppose I was asked to solve: $$5x+6=10 \mod 17$$ I would get this far with normal algebra: $$x = \frac{4}{5} \mod 17$$ But now I have a non integer expression ($4/5$) where it does not belong. What am I missing here? I think I have made a…
jsj
  • 535
0
votes
2 answers

N-bit number $m'$ , such that $m' = m \mod 2$

I was reading a paper about fully homomorphic encryption and I stumbled upon the following text: if To encrypt a bit $m ∈ \{0,1\}$, set $m′$ to be a random N-bit number such that $ m′ = m \mod 2$. I don't understand this. From what I understand…
cipher
  • 207
0
votes
2 answers

How to find the total no. of cards if I know the numbers left on putting them in different stacks?

I have a collection of cards, then: If I put them in stacks of 2, I have 1 left If I put them in stacks of 3, I have 1 left If I put them in stacks of 4, I have 1 left If I put them in stacks of 7, I have 0 left So how many cards do I have??
Ghost
  • 759
0
votes
1 answer

Is there a way of calculating the value on the opposite side of a set in modular arithematic?

So mod 12 is like a clock- if the hand is pointing at 12 is there a way of calculating the number on the opposite side of the clock? ( ie. 6 ) For mod 12 it's easy but for a clock with thousands of units is there a way of calculating that value?
ogginger
  • 113
0
votes
3 answers

Why doesn't -101 mod 13 = 10?

Following the formula found here (r = a - (a/b)b) I have been successfully finding the remainder for several problems, but when I try to solve -101 mod 13, I get the answer 10 even though it should apparently be 3. 101/13 = 7.769, ignore everything…
0
votes
1 answer

Possible to find in general a $c$ such that for two specific integers,$a$ and $b$, $a \equiv b \bmod c$?

A professor of mine gave us a question to think about regarding hashing and I have an idea, but it hinges on this being possible and I'm not too sharp on modular arithmetic. To give an example, let's say $a = 243$ and $b = 1724$. Can we find a $c$…
0
votes
0 answers

How to solve using Fermat's Little Theorem on large numbers

Does anyone know how to solve $2032^{3366}\pmod{3359}$? So far I managed to get, $$ 2032^{3366} \equiv 2032^{8}\pmod{3359} $$ Now I am not sure what to do next.
Raihan
  • 11
0
votes
2 answers

Show that if $x^3 + y^3 = z^3$ then 3 divides one of $x,y,z$

I can do this problem by going over all the cases mod 7. Is there any other way to do it?. I think this way is too long , so I wonder if there is another way to do it or some way to simplify my solution.
ElChavoDelOcho
  • 271
  • 2
  • 6
0
votes
3 answers

Wrong answer by modular division.

I want to calculate (6092427983/4)%(10^9+7). If preforming modular division by formula (a/b)%m = a*(b^-1)%m i get answer 273106987, and if i solve without modular division i get answer 523106988. Why are the answers different , even all the…