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

(Modular Arithmetic) Congruences With Exponents

I am trying to find the following: The least positive integer $n$ for which $3^n \equiv 1$ (mod $7$) And hence $3^{100}$ (mod $7$). The least positive integer $n$ for which $5^n \equiv 1$ (mod $17$) or $5^n \equiv -1$ (mod $17$) And hence evaluate…
The Pointer
  • 4,182
2
votes
1 answer

For each of n = 84 and n = 88, find the smallest integer multiple of n whose base 10 representation consists entirely of 6's and 7's.

For each of n = 84 and n = 88, find the smallest integer multiple of n whose base 10 representation consists entirely of 6's and 7's. How would I go about solving this? I was thinking about modular arithmetic, but I'm not too familiar with it. I…
Ayo
  • 111
2
votes
1 answer

Find n such that $2^{n} \equiv x\mod 3^{k}$

It looks like for every $k \ge 1$ and x is not a multiple of 3, $2^{n} \equiv x\mod 3^{k}$ as a unique solution (modulo $2 \times 3^{k-1}$). How to prove it? How to find such n given k and x? Thanks.
Damien
  • 294
2
votes
1 answer

$p\mid a^2+b^2$ Prove that $p\mid a$ and $p\mid b$

Let $p=4k+3$ be a prime number and $a,b\in\mathbb{N}$ so that $p\mid a^2+b^2$ Prove that $p\mid a$ and $p\mid b$ I tried to use Fermat's little theorem, but I don't know what to do next.
2
votes
1 answer

Does this modular congruence have a solution?

Prove that every number in $\mathbb{Z}$ is a solution to the congruence $$x^7 − 2x \equiv x \ \ (\operatorname{mod} 42)$$ As far as I can see, this congruence does not have any solutions (for example if we take $x=3$, the output is incorrect),…
2
votes
6 answers

Last three digits of $6^{2002}$

Find the last three digits of $6^{2002}$. I did some work and figured out that the last two digits is 36. Can anyone help me with the hundredth digit? By the way, I used modular arithmetic and the recursion method for the tens digit, but it fell…
KingLogic
  • 1,441
2
votes
1 answer

Quickest way to find smallest positive integer solution to $ax\equiv b\mod m$

Let $I(a,b,m)$ be the smallest postive integer solution $x$ to the modular equation $$ax\equiv b\mod m.$$ What is the quickest way to find $I(a,b,m)$ for given integers $a,b,m$? I know how to find it with the generalized euclidean algorithm, but is…
Ethan Splaver
  • 10,613
2
votes
4 answers

Simplify $3^{2018}\pmod{31}$

I need to simplify $3^{2018}\pmod{31}$. I just want to make sure I did this correctly. $\phi(31)=30$ ,so $\frac{2018}{30}= 67$ remainder $8.$ Then $ \equiv3^{67\cdot30+8} \rightarrow \equiv (3^{30})^{67}\cdot3^8$ And $3^{30}\equiv 1\pmod{31.}$ Thus…
Killercamin
  • 801
  • 4
  • 17
  • 39
2
votes
0 answers

Last digits of iterated triangular numbers

First, let me explain what I mean by iterated triangle numbers: The triangle of a number $n$ is the sum of all numbers from 1 to n, i. e. $1+2+...+ n$. Iterated triangle numbers are what you get if you repeat this process (that is, find the triangle…
Allam A.
  • 229
2
votes
2 answers

Prove if $p\nmid a$ then $a^{p^2}\equiv a^p\bmod p^2$

Prove if $p\nmid a$ then $a^{p^2}\equiv a^p\bmod p^2$. I tried to use Fermat's little theorem and I got $a^{p^2}\equiv a\bmod p^2$ but I don't know how to prove the main result.
2
votes
1 answer

Least positive integer satisfying congruence relation

How do I go about finding the solution to this problem? Find the least positive intger, $M$, such that $M^{49}\equiv21 \pmod{209}$. I'm thinking we need to rewrite the left hand side somehow to reduce the exponent, but I don't know how since $M$ is…
user2157416
  • 159
  • 7
2
votes
2 answers

Substitution in congruence relations

I'm a noob to discrete math, and have a basic question for a sanity check. From studying basic modular arithmetic, the following are properties of congruences: 1) $a \equiv a \pmod{n}$ 2) $a \equiv b \pmod{n} \implies b \equiv a \pmod{n} $ 3) $a…
leontp587
  • 149
2
votes
2 answers

Repeated multiplication in modulo $n$ that eventually yields every number

Given an initial number $m$ and a modulo $n$, is there a way of determining some constant multiplier $k$ so that $(m \times k^x) \mod n$ will eventually yield all integers in $[1,n]$ by incrementing $x$? Alternately, if I instead do $(m \times x)…
Jon Gjengset
  • 145
  • 5
2
votes
0 answers

Modular arithmetic with powers and prime numbers

I have been struggling with this problem for a long time. $$ 19^9 \mod 1189 = 1113\\ 29^9 \mod 1189 = 522\\ 39^9 \mod 1189 = 308\\ x^9 \mod 1189 = 377 $$ the answer is $87$. It can be easily found by factorization (the fact that $1189=29 \times 41$…
padawan
  • 290
2
votes
1 answer

$a^b \mod m$ - cycles

Equation: $a^b \mod m$ for subsequent values of $b$ and $a$ produces a cycles. For example: $m = 3$. We have $a > 1$ and $b > 4$ ($b$ is always large enough). $2^5 \equiv {\color{red}2} \pmod 3$ $2^6 \equiv {\color{red}1} \pmod 3$ successive…
Aurelio
  • 479