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

Primes dividing Fibonacci mod 4

I'm trying to do the following question and am a bit stuck. Would appreciate a hint over a full solution if possible. Here $F_n$ denotes the $n$-th Fibonacci number, and at this point in the question we have already shown…
2
votes
2 answers

System of congruences when $gcd(m,n) \not= 1$

I have to solve this system but I don't know what I did wrong, since the result should be: $ x \equiv19\;(mod\;56)$. $$ \begin{cases} x \equiv 3\;(mod\;8) \\ x \equiv 19\;(mod\;28) \\ \end{cases}\\ $$ $$ 3 + 8k = 19 + 28h\\ 8k-28h =…
Shyvert
  • 177
2
votes
1 answer

Converse of an equation of Modular Arithmetic

We know that if, $a\equiv b \pmod n$ then $$a^n\equiv b^n \pmod n$$ Is the converse true for odd $n$? The converse isn't true for even because $3^4 \equiv 1^4 \pmod 4$ but $3 \equiv 1 \pmod 4$ isn't true. If the converse is true for odd n then give…
Hasin
  • 21
2
votes
1 answer

What pairs of x and y give a multiple of 1000?

I am playing this cool game called Territory Idle. In this game, two types of buildings can earn resources. Some earn a resource for each worker while others add one per worker of the resource. Here is an example: I have two temples, each with 70…
n49o7
  • 123
2
votes
1 answer

Given $a^b \pmod {c}$, $a^b \pmod {d}$, $a^b \pmod {e}$, how can $a^b mod (c*d*e)$ be deduced?

This question covered large exponents on the $b$ side. What about the $m$ side? Given: $$a^b \pmod m$$ where $m$ is a large compound number. For example: Given $$5^{2003} \pmod {7} \equiv 3$$ $$5^{2003} \pmod {11} \equiv 4$$ $$5^{2003} \pmod {13}…
2
votes
3 answers

Solving a system of modular equations

I am trying to solve this system of equations: $24x ≡ 12 \hspace{5pt} (\mathrm{mod} \hspace{2pt} 63)$ $x ≡ 2\hspace{5pt} (\mathrm{mod} \hspace{2pt} 27)$ So I know that the second equation is equivalent to $x=27y+2$, but when I plug it into $24x ≡…
user720998
2
votes
1 answer

Help me find the pattern/idea of this

I'm sorry for my bad english. English is not my main language. I've been trying to study this and its patterns for a while. You can see this in many ways, but the first way I saw this was from a geometrical point of view. I saw this as convexes…
2
votes
1 answer

Inverse of integer power in modulo ring

For a prime $n$ and a generator $g$ of the multiplicative Group $\mathbb Z/n\mathbb Z$, $b = g^a \mod n$ is a bijection for $a \in \{0,\dotsc,n-2\}$ and $b \in \{1,\dotsc,n-1\}$. But how can I calculate its inverse? Concrete example in…
pascal
  • 177
2
votes
3 answers

Calculate $x^2 \equiv -1 \mod 169$

Calculate $x^2 \equiv -1 \mod 169$ By hand I checked that $x^2 \equiv -1 \mod 13$ gives these solutions: $$ x \equiv 5 \mbox{ or } x \equiv 8 \mod 13 $$ Let say that I take $x \equiv 5 \mod 13$ so I have $$ x\equiv 13k+5 \mod 169 \mbox { for…
user677339
2
votes
4 answers

Proving the congruence $a^3\equiv 0,1,8\pmod{9}$

I'm having some issues solving the following example - For any positive integer, prove that: $a^3 \equiv x \space mod \space 9$ where $x = \{0, 1, 8\}$ What I usually do with such examples is attempt and apply mathematical induction and create a…
Stefan
  • 69
2
votes
0 answers

Solutions to $n^2\equiv1 \mod a$

I was wondering if anyone had a simple way of finding the solutions to $$n^2\equiv1 \mod a.$$ I think I read somewhere that the solutions are always $$n\equiv\pm1 \mod a,$$ but the proof seemed inaccessible to me. Thanks!
2
votes
3 answers

Arithmetic series has first term

An arithmetic series has first term a and common difference d. The sum of the first 31 terms of the series is 310 a) Show that a + 15d = 10 b) Given also that the 21st term is twice the 16th term, find the values of a and d.
Bibi
  • 29
2
votes
0 answers

Is $Z_n^*$ (multiplicative group mod $n$) mod a divisor $m$ ($m|n$) equal to $Z_m^*$?

The closest I could find was this archived reddit post. There I think they prove that $Z_n\setminus Z_n^{*}$ can be made isomorphic to $Z_m^{*}$. Question: Let m|n. ($Z_n^{*} \mod m) = Z_m^{*}$ (as sets, not ring isomorphism or any other stronger…
2
votes
2 answers

Number of solutions to a set of homogeneous equations modulo $p^k$

Let $p$ be a prime number and $k$ be a positive integer. How do I determine the number of solutions to a set of equations in variables $0\leq x_1,...,x_n
user3533
  • 3,285
2
votes
2 answers

How to solve following problem?

I know it might have something to do with modular exponentiation, but after extensive search and reading, I am completely dumbfounded. $$\text {Let}\; N = 12 = 2^2 + 2^3$$ Given that $M^2 \equiv 51$ (mod 59), What is $M^{12}$(mod 59)?
Aman Khan
  • 119
  • 1
  • 1
  • 8