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
1
vote
2 answers

Prove that every positive integer is congruent to the sum of its digits modulo 3.

Prove that every positive integer is congruent to the sum of its digits modulo 3.So I start with rewrite as $n = c_r 10^r + c_{r-1} 10^{r-1}...$?
1
vote
2 answers

Prove this modular congruency?

Prove that $2^{2x} \equiv 1 \mod 3$ for any integer $x$?. I know this is true but is there a nice way to prove it?
jg mr chapb
  • 1,502
  • 1
  • 13
  • 44
1
vote
2 answers

Suppose that n is an integer divisible by 24. Show that the sum of all the positive divisors of n−1 (including 1 and n−1) is also divisible by 24.

Suppose that n is an integer divisible by 24. Show that the sum of all the positive divisors of n−1 (including 1 and n−1) is also divisible by 24.
F. Ni
  • 13
1
vote
2 answers

Elementary proof regarding 6k mod p

Is there a simple (read primarily elementary) proof that performing $6k \mod p$ where $k$ runs from $1$ to $p$ will always return the sequence of counting numbers from $[0,1,2,...,p-1]$ (though not in that order), for all $p >= 5$?
alfreema
  • 115
1
vote
3 answers

The product of $2×653×733×977$ has each digit exactly once except for one, which one is it?

The product of $2×653×733×977$ is a number with nine digits and it contains every digit once except for one, which digit is that? I noticed that it is a product of primes, but so far I cannot solve it without multiplying it out. I suspect I can…
GuPe
  • 7,318
1
vote
1 answer

Conceptual Query related to Modulo arithmetic

Came across an expression given below $$321^{984} \equiv 6^{984} \equiv(-1)^{984}\equiv 1 \pmod{7}$$ Now $321^{984} \equiv 6^{984} \pmod{n}$ is understood and $6^{984} \equiv (-1)^{984} \equiv 1^{984} \pmod{n} \equiv 1 \pmod{n}$ but then how is…
Ankit
  • 63
1
vote
3 answers

Is there a quicker way to get $ 207^{321} \mod 7 $

For $207^{321} \pmod{7},$ I got $$ 207^{321} = 207^{6\cdot 53+3}$$ and $$207^{\Phi(7)} \equiv 207^6 \equiv 1 \pmod{7}$$ by Euler's Theorem. Then $$207^3 \equiv 4^3 \equiv 1 \pmod{7} $$ Is there any simpler way? I'm also not sure about the format…
1
vote
1 answer

When does $g^{\sum_i e_i} \equiv g^e \mod m$ hold?

The question is simple: given $\sum_i e_i \equiv e \mod m$, what do we know about $g^{\sum_i e_i} \mod m$? I know it's certainly not always $g^e \mod m$ as the following counterexample shows: Let $e_1 = 2, e_2 = 3, m = 5, g = 2$, $g^{e_1} \equiv 4…
qweruiop
  • 374
1
vote
1 answer

Deciding if $m \not \in \{x^2 \bmod p : x \in \mathbb N\}$, also cardinality

Let $S_p = \{x^2 \bmod p : x\in\mathbb N\}$, with $p$ prime. Is there an efficient way to determine if an arbitrary $m \not \in S_p$, where $m \in\mathbb N \bmod p$, without generating $S_p$? E.g. $S_5 = \{0, 1, 4\}$, $m \in \{2, 3\}$. Also is there…
1
vote
3 answers

How to evaluate last nine digits of $(2^{120} - 1) / 3$ without any intermediate value exceeding $2^{32}$

Here's what I know: The modular inverse of 3 for the modular base of $10^9$ is 666,666,667 The last nine digits of $2^{120}$ is 280,344,576. The product of the two exceeds $2^{32}$ (it is around $2^{57.375}$) $2^{120}$ - 1 is divisible by 3, but…
1
vote
2 answers

proofs involving congruence of integers

Let n, m be integers. Prove that if n ≡ 1( mod 2) and m ≡ 3( mod 4), then n^2 +m ≡ 0(mod4) My thought process is that n=3 and m=7 so n^2 would be 9+7 but then i do not believe that would equal 0(mod4) which i think would equal 4. Any direction…
Cole
  • 93
1
vote
6 answers

What is $5^{-1}$ in $\mathbb Z_{11}$?

I am trying to understand what this question is asking and how to solve it. I spent some time looking around the net and it seems like there are many different ways to solve this, but I'm still left confused. What is the multiplicative inverse of…
Tashor
  • 11
1
vote
1 answer

Integers with cubes ending $\ldots888$.

This is a coding question.Here we have to find the $k$-th value in which we get $888$ as the last three numbers for a cube of a number. For example, if $k=1$ the first value with last three numbers as $888$ is $192 ^3$.Then if $k=2$ the second value…
navroze
  • 19
1
vote
1 answer

Modular arithmetics: one sequence is equal to another read backwards

I was doing some music theoryzing (circles of fifths and fourths) and found an interesting problem. Suppose, we have $2$ sequences: A and B. A $a(i+1) = a(i) + 7 \pmod {12}$ $a(0) = 0$ As $7$ and $12$ are coprime, period of this sequence will be…
user4035
  • 351
1
vote
2 answers

Computing a remainder of big numbers using modular arithmetic

I have a kind of confusion dealing with modular arithmetic, specially regarding remainders. I am aware of Euler/Fermat theorem that says: if p is prime, then 2^(p-1) is congruent to 1 module p. However, supose that p is not prime. How is the best…