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

Find the remainder when $2^{837259739}+ 3^{23456}$ is divided by $31$

for $2$ I was able to solve it by going from $$(2^5)^{167451947} \cdot 2^4$$ which is congruent to $1(\mod 31)$ and $16(\mod31)$ respectively. I just don't know if I'm doing the $3$ part correctly. Would $(3^3)^{7818} \cdot 3^2$ be $27(\mod31)$…
Kayy Wang
  • 87
  • 5
2
votes
1 answer

Is $n^{800}= 1 \mod{800}$ given that $n$ is relatively prime to 800?

I was playing around with some numbers and it seems that for a lot of numbers that are relatively prime to 800 $$n^{800} = 1 \mod{800}$$ is this true in general, or is it just coincidental? Is it true that $$n^k=1 \mod{k}$$ where $n,k$ are…
Peter Foreman
  • 19,947
2
votes
6 answers

Calculate $100^{1207} \mod 63$

I try to solve this question: Calculate $100^{1207} \mod 63$. There is the hint that i should calculate $100^{1207} \mod 7$, $100^{1207} \mod 9$, which is easy for me, but I don't see the relationship between this to questions. I guess it must have…
eriae
  • 21
2
votes
1 answer

How is this done?

The question here: A number when successively divided by 9, 11 and 13 ... I found the answer to it in a book and this was the answer: The least number that satisfies the condition= 8 + (9×9) + (8×9×11) = 8 + 81 + 792 = 881 I brute forced the…
2
votes
2 answers

Replacing mod in equation

I'm trying to find the smallest integer $x$ such that $2^x \equiv 166 \pmod {330}$. It is result of a problem I am solving and I am wondering is there a way to find suitable $x$ without trying all possible values? I've noticed that $x=20$…
eXPRESS
  • 203
2
votes
3 answers

high power congruences finding $x$

trying to solve: $$x^{13} \equiv 11 \pmod{135}$$ I came to the fact that $x = 11^{59}$ but its in mod $72$ and needs to be converted to mod $135$ any suggestions? I'm not sure how to change it to mod $135$ with such a large number
2
votes
3 answers

Proving $4^{47}\equiv 4\pmod{12}$

I know this is a simple exercise, but I was wondering if I can make the following logical jump in my proof: We see that $4\equiv 4\pmod{12}$ and $4^2\equiv 4\pmod{12}$. Then we can recursively multiply by $4$ to get $4^{47}\equiv 4\pmod{12}$.
2
votes
2 answers

solve modular arithmetic equation

How do I solve this equation $L = D + [D:4]$ $L$ is a known integer obtained previously; $D$ is an integer; $[D:4]$ is the quotient part of ($D/4$.) At first glance, I did not know how to solve this equation as I have never seen this type in my…
Ali_R4v3n
  • 121
2
votes
1 answer

Solving $472x ≡ 32 \;(\text{mod } 92)$: How to solve when $a$ is greater than $m$

I'm not sure where to begin here. I think that I can change the $472x$ to be $12x$ because they should be equal in mod $92$. Then, I believe I can simplify the equation to be: $3x ≡ 8 \; (\text{mod } 23)$
user52640
  • 105
2
votes
0 answers

eliminate very kth element in mod n... save a given element for last

We are given $1,\ldots,n$ numbers. Let's say we are to save a given number element $k$ for last in elimination. We start eliminating them in the following manner. I eliminate $1$ at first. Then eliminate the next $k$th element (index $k+1$). And…
Fluvid
  • 201
2
votes
2 answers

Solving $m^3 \equiv n^6 \pmod{19}$

I'm studying for a first year Discrete Mathematics course, I found this question on a previous paper and am lost on how to solve: Let $n$ be a fixed arbitrary integer, prove that there are infinitely many integers $m$ s.t.: $m^3 \equiv n^6…
Seb Leach
  • 21
  • 2
2
votes
0 answers

For which $m$ does $x^n \equiv y^n \pmod{m}$ imply $x \equiv y \pmod{m}$?

How would I find, given an integer $n$, for which values of $m$ (also integer) does $x^n \equiv y^n \pmod{m}$ imply $x \equiv y \pmod{m}$?
user609740
  • 21
  • 3
2
votes
2 answers

Linear Congruences in One Variable.

I am currently learning Linear Congruences in One Variable. This sections starts with the example $$2x≡3\bmod 4$$ It just states that the congruence is not solvable. I was wondering if any could show me how to solve this to get such answer.
Hidaw
  • 971
2
votes
1 answer

Powers of 3 modulo powers of 2

This question is probably simple, but it has been a couple of years since I have practised group theory. Let $d\ge 2$ be an integer. Does there exist an integer $k\in\mathbb{N}$ such that $$ 3^d +1 = 2^k. $$
Marc
  • 6,861
2
votes
1 answer

modular arithmetic : $((a-b)/c)\bmod m = {}$?

How can I express $((a-b)/c) \bmod m$ in terms of $a \bmod m$, $b \bmod m$ and $c \bmod m$?
Jatin
  • 123