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

What is the modular representation of an integer?

What is the modular representation of an integer using a set of primes? More specifically, a problem on my homework asks to convert 49 to a modular representation using primes 7,11,13,17. Would appreciate a general solution.
James
  • 1,320
3
votes
3 answers

How to calculate modulo of high power of 2

I know there are other such topics but I really can't figure how to calculate the following equation: 2^731 mod 645. Obviously I can't use the little theorem of Fermat since 645 is not a prime number and I can't also do the step by step rising of…
3
votes
3 answers

Can't come even near to the solution.. Can somebody take a look?

Fermat's little theorem states that if $p$ is a prime number, then for any integer $a$, the number $a^p − a$ is an integer multiple of $p$. In the notation of modular arithmetic, this is expressed as $$a^p \equiv a \mod p.$$ Use Fermat's little…
3
votes
3 answers

How does Modulo Arithmetic work

question $\frac{a}{b}$=Q (remainder) R why is A mod B = R i just dont understand how modulo arithmetic work in general after researching about it. It seems as if the function (mod) only spits out the remainder but when i looked at $x^5 = 11 \mod…
John Rawls
  • 2,685
3
votes
2 answers

congruence proof

I am looking into congruences for school and I have trouble understanding on how to prove this (i understand modules, congruences but don't know how to prove it). I need to prove that if this congruence is true: $$a c \equiv b c \pmod m$$ then also…
blejzz
  • 133
3
votes
2 answers

Modular Arithmetic - what did I do wrong?

I'm trying to solve 17y=1 (mod 57). Since gcd(17,57)=1 and 1 divides 1, they are relatively prime (coprime) and so the modulus equation above indicates that there will be a solution (exactly one residue class of mod57). My first attempt: 17y≡1…
3
votes
4 answers

How many solutions does equation $6x=14 \bmod 35$ in $\mathbb{Z}/35\mathbb{Z}$ have?

Yes, this is a homework problem. And no, I'm not asking for the answer to this. I just want to understand how to tackle this type of problem. What are the steps towards finding the solutions? My class is not much help and I am lost! Any help is…
3
votes
2 answers

Nested modular arithmetic

I can't seem to grasp if/why you can have repeatedly take mod's at intermediate steps and still have the result be true, looking at the following equivalence: $[u -c*(a^{|u|-1})] \mod{p} = [u-c*(a^{|u|-1}\mod{p})] \mod{p}$ (If c is the first digit…
Jess
  • 291
3
votes
13 answers

Prove that for all odd integer $n, n^{4}=1\pmod {16}$

My answer: $n=2k+1$ $n^{4}=(2k+1)^{4}$=$16k^{4}+32k^{3}+8k^{2}+24k+1$. I do not know how to conclude; really needed help here.
Surdz
  • 627
3
votes
1 answer

$a^{100}-1$ is divisible by $1000$.

While working on competition math, I came upon the following problem: How many integers $x$ from $1$ to $1000$ are there such that $x^{100}-1$ is divisible by $1000$? This was very confusing, as the numbers that I had to deal with were so large, so…
RK01
  • 803
3
votes
1 answer

Modular arithmetic system $x \equiv 2 \pmod{7}$ and $x \equiv -5 \pmod{22}$

The task is to find all integers $x$ such that $x \equiv 2\pmod 7$ $x \equiv -5\pmod {22}$ My guess is that the Chinese Remainder Theorem may help. I've never done a question like this that had a negative value in one of the equations before. If…
Amous
  • 235
3
votes
2 answers

Calculating the summation of $n \bmod i$

This is a codeforces question, where we have to calculate the sum of $N\bmod i$ modulo $10^9 + 7$ where $i$ goes from $1$ to $M$. $N$ and $M$ are very large values about $10^{13}$. They have provided an editorial for this question, but I dont…
karun
  • 45
  • 1
  • 3
3
votes
3 answers

Wilson's Theorem: (n-1)! is congruent to -1(mod n) implies that n is prime.

I have researched Wilson's theorem several times over stack exchange. I would only like to prove one direction. This seems to be a good explanation: Prove that $(n-1)! \equiv -1 \pmod{n}$ iff $n$ is prime However, on their explanation, the author…
3
votes
1 answer

Modulo Distribution With Powers

Why is it true that $x^{ab}\mod{n}=(x^a\mod{n})^b\mod{n}$? I understand that if I substitute $z$ for $x^a$, I get: $z^b\mod{n}=(z\mod{n})^b\mod{n}$ $=(z\mod{n})_1*(z\mod{n})_2*...*(z\mod{n})_b\mod{n}$ On Wikipedia, I see that one of the distributive…
3
votes
1 answer

Finding the smallest $n$ to modulo a set with no collisions

Given a set of positive integers with no collisions (that is, every element is unique), $A = \{\ldots\}$, how can I find the smallest modulus, $n$, so that $B = A \pmod n$ has no collisions?
built1n
  • 111