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

Remainder of $2^{100} (\mod\ 89)$

I am having trouble coming to the answer on this question: Find the remainder when $2^{100}$ is divided by $89$. (Hint: Simplify $2^{10} \pmod{89}$ first.) So I went with the hint and found $2^{10} = 45 \pmod{89}$, but I don't think I would want to…
Carolyn
  • 255
2
votes
1 answer

Prove that $11^{2n}+5^{2n+1}-6$ is divisible with $24$ for $n∈ℤ^+$

Prove that $11^{2n}+5^{2n+1}-6$ is divisible with $24$ for $n∈ℤ^+$ I've been trying to solve it by using modulo; $11^{2n}+5^{2n+1}-6≡ (11^2 mod24)^n + 5*(5^2mod24)^n-6 = 1^n + (5*1^n)-6 = 0$ Is this the right way to tackle the problem? I am not…
itZCoZ
  • 45
2
votes
1 answer

How do I find the smallest positive integer $a$ for which $a^n \equiv x \pmod{2^w}$?

$x$ is fixed odd positive integer value. $n$ and $w$ are fixed positive integer values. $a$ is positive integer value. I am interested for $n=41$ and $w=160$, but would appreciate a general algorithm. I know how to find any $a$ for which $a^n \equiv…
desowin
  • 23
2
votes
2 answers

Solve for $b$ in $2^b\bmod11=7$

If I have the equation- $$ 2^b \bmod 11 = 7 $$ How can I solve this to find out what $b$ is? I know $b$ is $7$ but I'd like to know how this is done mathematically rather than guessing.
2
votes
1 answer

Is it possible to (uniquely) reverse modulo operation by solving multiple equations with the same original integer?

I've tried searching but I haven't been able to find an answer. There are similar questions about reversing modulo operation here on stackexchange, but I haven't found a question which is applicable to my problem. All answers I've found on reversing…
Tergo
  • 23
2
votes
1 answer

Does $x^n+1 \equiv 0 \pmod{n}$ imply $\text{gcd}(x+1,n)>1$?

Does $x^n+1 \equiv 0 \pmod{n}$ imply $\text{gcd}(x+1,n)>1$? My feeling is that it shouldn't be too hard to prove, but I just can't figure it out. For $n$ prime it is clear since $x^n \equiv x \pmod{n}$ in that case.
Pjotr5
  • 2,187
  • 1
  • 13
  • 17
2
votes
3 answers

How can I solve $7^{77}\mod 221$

How is it possible to solve this without calculator etc.: $$7^{77} \mod 221$$ I started with: \begin{align} 7&\equiv 7 \mod 221 \\ 7^2 &\equiv 49 \mod 221 \\ 7^4 &\equiv \ ? \mod 221 \end{align} Sure i can calculate this by my own, but is there a…
greedsin
  • 571
2
votes
2 answers

Patterns in Mods of Successive Powers

I was working on a problem for Project Euler and I made an assumption that led to me solving the problem. My assumption was that if we take mods of successive powers with a constant modulo, they will follow a pattern. For example: $$3^1\equiv 3 \mod…
2
votes
2 answers

Clarification on a Inverse modulo exercise

Find integers $x$ and $y$ such that $49x + 100y = 1$. Which, if either, is the inverse of $49$, modulo $100$? I know the answer to this is $x = 49$ and $y = -24$, but how do I arrive at that? The argument starts with: $$100 = 1(100) +…
2
votes
1 answer

Fermat's Little Theorem Induction $a^{(p_1 -1)(p_2 -1)\dots(p_n -1)} \equiv 1 \pmod{M}$

Let $M = p_1 p_2 \cdots p_n$ be a positive integer with prime factorization. Let $\gcd(a,M) =1$. Prove that $a^{(p_1 -1)(p_2 -1)\cdots(p_n -1)} \equiv 1 \pmod{M}$, by induction. The base case is just Fermat's Little Theorem but I am unsure how to…
2
votes
4 answers

Calculating the modulus for a large value

I'm building a calculator for International Bank Account Numbers (IBAN) but I'm having trouble calculating the modulus for a big number. That is to say, my results are not the same as that of the examples I have. To calculate the IBAN checksum I…
2
votes
2 answers

Divisibility criteria of number 7

How do I prove the divisiblity criterium of number seven having $a_{n}*10^n + a_{n-1} *10^ {n-1} + ... + a_3*10^3 + a_2*10^2 + a_1*10 + a_0$ For example, I underestand that in the divisibility criterium of 3 we have to use mod 3 to do it and the…
user282580
2
votes
1 answer

Finding $y$ so that $y^2 + x^2 \equiv 1 (\mod x + y)$

A number of my friends at school came to me with the following problem which I was unable to solve. For any integer $x$, there exists $y$ so that: $$ x^2 + y^2 \equiv 1 \mod x + y$$ I understand I am trying to solve for two integers $y$ and $q$ so…
2
votes
3 answers

In modular arithmetic, could π be represented as an integer?

If I have a field of all real numbers on $[0,p) (\mod p)$ under normal addition and multiplication where $p$ is a prime number, it can be shown that all integers have multiplicative inverses that are also integers. This means all rational numbers…
Zach L
  • 262
2
votes
4 answers

Prove or disprove: For all positive integers n and for all integers a and b, if a ≡ b mod n, then a^2 ≡ b^2 mod n.

Prove or disprove: For all positive integers $n$ and for all integers $a$ and $b$, if $a \equiv b \mod n$, then $a^2 \equiv b^2 \mod n$. Prove or disprove: For all positive integers $n$ and for all integers $a$ and $b$, if $a^2 \equiv b^2 \mod n$,…
hello
  • 37