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

Evaluating the congruence $(1+195) \pmod 7$

$$(1 + 195) \pmod 7 \equiv \quad ?$$ How would I get the answer? Because when I divide $196 / 7$ I get $28$ which is not a decimal to multiply by $7$.
MethodManX
  • 1,127
0
votes
1 answer

Number Theory-Find all natural numbers n such that

Find all positive integers n, such that \begin{equation} 22^n+8^n-11^n-3^n \equiv 0\ (\textrm{mod}\ 209) \end{equation} My attempt so far: \begin{equation} 11^n(2^n-1)\equiv 0\ (\textrm{mod}\ 209) \Leftrightarrow\ (2^n-1)\equiv 0\ (\textrm{mod}\…
Jut3
  • 21
0
votes
0 answers

How many possibilities are there for the number of solutions of a linear congruence modulo 20

So I was given this question and I'm not very good at this if anyone could provide a little help I know that $ax\equiv b\pmod{20}$ and by using $gcd(a,20) = 1$ unique solution and $gcd(a,20) = 2,4,5,10,20$ what do I do next? Do I test out all of the…
beepboop
  • 119
0
votes
0 answers

Hungerford section 2.1: Find all the solutions of $6x \equiv 9 \pmod{15} $

I am new to working with modular equations and am trying to find all the solutions to the equation $ 6x \equiv 9\pmod {15} $, here's what I have so far: $6x \equiv 9 \pmod{15}$ means $6x-9=15m$ for some $m\in \Bbb Z$.…
0
votes
0 answers

Time complexity of solving a linear congruence of $A p + C \equiv 0 \pmod {2^b}$ form

I'm curious about the best possible computational time complexity of solving a linear congruence of the form $$ A p + C \equiv 0 \pmod {2^b} $$ where $A$, $b$ and $C$ are all positive integers and $p$ is the variable we are looking for. $A$ is…
0
votes
2 answers

Modular Arithmetic Congruences

Can someone please help me on this problem in modular Arithmetic Congruences I ran into this problem on aops alcumus If $3x+7\equiv 2\pmod{16}$, then $2x+11$ is congruent $\pmod{16}$ to what integer between $0$ and $15$, inclusive?
0
votes
0 answers

$7^{21}\cdot 2^{50}+a$ is divisible by $9$

Find the smallest value of $a\in\mathbb{N}$ such that $7^{21}\cdot 2^{50}+a$ divisible by $9$. The only thing I know is that an integer is divisible by $9$ is the sum of its digits is divisible by $9$.
stefano
  • 625
0
votes
1 answer

Multiplying the residue classes mod n by a coprime

I noticed an interesting result when playing around with mods. If I take all the residue classes of $n$ and multiply each of them by an integer $q$ such that $n$ and $q$ are coprime, then each residue class maps to a unique new residue class. For…
0
votes
1 answer

Is there any inverse operator for mod?

It seems to me that operators usually come in pairs: Plus and minus, Multiplication and Division, Exponentiation and Logarith, Derivative and Integral. Is there such inverse operation of modulus?
0
votes
1 answer

If $x\equiv a\pmod{n}$, prove that either $x\equiv a\pmod{2n}$ or $x\equiv a+n\pmod{2n}.$

If $x\equiv a\pmod{n}$, prove that either $x\equiv a\pmod{2n}$ or $x\equiv a+n\pmod{2n}.$ Well I am a bit stuck in this congruence problem. I tried out :- $n\vert x-a$ so for $2n|x-a$, $x-a$ must be even but I am not able to prove what if $x-a$…
arnav_de
  • 699
0
votes
0 answers

Is $2^{125} \bmod 257$ $=225$

I did how $256=-1$ mod $257$ and $2^8=256$ then $(2^8)^{15}=-1 $ mod $257$ and i conclude that $2^{125} \bmod 257 = 225$
0
votes
1 answer

Number Theory - Find all $n$ such that $x^2 ≡ x$ (mod $n$) for $x$ ≡ 0,1 (mod $n$) only

When $n = p^k$, where p is prime and k is a positive integer if $x^2 ≡ x$ (mod $p^k$), then $p^k$ divides $x^2-x = x(x-1)$, since $x$ and $x-1$ are coprime, $p^k$ divides either $x$ or $x-1$, so $x ≡ 0$ (mod $p^k$) or $x ≡ 1$ (mod $p^k$). When n is…
0
votes
1 answer

Proving that $\sum_{n=1}^{p} n^m \equiv 0 \pmod{p}$

Suppose $p$ is a prime number not equal to $2$ and $m$ is a positive integer, where $$p \nmid 2^m - 1.$$ Prove that $$\sum_{n=1}^{p} n^m \equiv 0 \pmod{p}.$$ I first wrote out the sum, which gave me $$1^m + 2^m + \ldots + p^m \equiv 0 \pmod{p}.$$…
0
votes
0 answers

A better method to prove that $97 \mid 2^{48}-1$

Proving that a given numbers is divisible by an other number is often simple but when it comes to big numbers i don’t know how to deal with them. Prove that $97 \mid 2^{48}-1$. My Attempt: $$2^{12} \equiv 22 \mod 97 \iff (2^{12})^{4} \equiv…
PNT
  • 4,164
0
votes
0 answers

Binomial expansion and congruence?

I have come across at a proof in the book (I'm not writing it all down) but at the last lines it says: $9(73+8)^n + (73-9)8^n$ Is congruent to $9x8^n - 9x8^n$ is congruent to 0 (mod 73). What i don't get is that how is $9(73+8)^n + (73-9)8^n$ when…
Asim
  • 328