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
8
votes
5 answers

Is there a name for theorem ,$x^a - 1 \equiv 0 \mod {(x -1)}$, and how is my proof?

I came to realise after practising some modular arithmetic that: $x$, $(x-1)$$\space$ are$\space$ co-prime$ \space$ $\wedge$ $\space$ $x$, $(x-1)$ $\in$ $\mathbb{N}$ $\implies$ $x^\alpha \mod (x-1)$ = $1$ : $\forall$ $\alpha$ $\in$ $\mathbb{N}$ What…
8
votes
2 answers

Addition, Subtraction, Multiplication and Division on both sides of congruence relation

This post is to clear some of the doubts related to modulo arithmetic. Addition on both sides $a \equiv b \pmod p \iff$ $(a+k) \equiv (b+k) \pmod p$ Subtraction on both sides $a \equiv b \pmod p \iff$ $(a-k) \equiv (b-k) \pmod p$ Multiplication…
Kiran
  • 4,198
8
votes
3 answers

Fractions in Modular Arithmetic

Suppose we have $$\frac{2}{3} \equiv x \bmod 5$$ I understand that the first step that needs to be made is: $$2 \equiv 3x \bmod 5$$ But from there I'm having a hard time understanding the logic of how to solve for $x$. Obviously, with simple numbers…
RedShift
  • 765
  • 3
  • 11
  • 28
8
votes
4 answers

Finding the least significant digit of a large exponential.

I am trying to find the least significant digit of $17^{{17}^{17}}$. I know that I need to use to use the properties of modular arithmetic and mod base 10, but I am not sure how to go about it. Please provide some hints/first few steps to help me…
Mark
  • 351
7
votes
6 answers

Show that if n divides a single Fibonacci number., then it will divide infinitely many Fibonacci numbers.

Show that if n divides a single Fibonacci number, then it will divide infinitely many Fibonacci numbers.
K.C.S.
  • 183
7
votes
5 answers

Basic question about mod

I'm having a tough time understanding why $(a^x \bmod p)^y \bmod p$ is equal to $a^{xy}\bmod p$. Does this have a mathematical proof? Please advise.
Ragavan N
  • 315
7
votes
1 answer

Proof that $3^n$ is never congruent to $7 \bmod 1000$

I’ve been reading Mathematics Galore! by James Tanton. He has a brief elegant and accessible proof of the existence of a power of 3 that ends in 001. He then asks if a power of 3 ever ends in 007. This is equivalent to asking if $3^n = 7…
7
votes
1 answer

Calculate fictional moon position in the sky

I think this would be considered a maths question rather than a physics one. For context, I am creating a calendar for a fantasy game that has $2$ moons. In my current case moon #1 orbital time is $28=(2*2*7)$ days, and moon #2 orbital time…
7
votes
5 answers

If the last 3 digits of $2012^m$ and $2012^n$ are identical, find the smallest possible value of $m+n$.

Let $m$ and $n$ be positive integers such that $m>n$. If the last 3 digits of $2012^m$ and $2012^n$ are identical, find the smallest possible value of $m+n$. Since the 100's digit is 0 in both cases, I just did $2012^m \equiv 2012^n \mod 1000$,…
space
  • 4,561
7
votes
4 answers

What will be the one's digit of the remainder in: $\left|5555^{2222} + 2222^{5555}\right|\div 7=?$

What will be the ones digit of the remainder in: $$\frac{\left|5555^{2222} + 2222^{5555}\right|} {7}$$
Ravi
  • 123
7
votes
8 answers

Equivalence class plain English

Can someone please explain in plain English what is meant by an equivalence class? I've been reading it over and over again and it just doesn't make any sense to me. I've tried looking up definitions online as well but they're too difficult to…
user497020
7
votes
4 answers

Does there exist a smooth approximation of $x \bmod y$?

I'm looking for a function $m(x,y)$ that smoothly approximates $x \bmod y$, and I'm assuming there would be some $n$ or $\varepsilon$ in the body of $m(x,y)$ that defines the degree of approximation such that as $n$ goes to infinity or $\varepsilon$…
Noman
  • 89
  • 10
7
votes
4 answers

How to find $3^{1000}\bmod 7$?

Sorry this is a really simple problem but I couldnt figure it out. I'm trying to find the value of $3^{1000}\bmod 7$. I know the actual value is 4, but I used a calculator. How would I simplify this problem to get the correct answer without a…
Snowman
  • 2,664
6
votes
3 answers

Find $ n\geq1 $ such that 7 divides $n^n-3$

Find $ n\geq1 $ such that 7 divides $n^n-3$. Here is what I found: $ n\equiv 0 \mod7, n^n\equiv 0 \mod7,n^n-3\equiv -3 \mod7$ no solution. $ n\equiv 1 \mod7, n^n\equiv 1 \mod7,n^n-3\equiv -2 \mod7 $ no solution. $ n\equiv 2 \mod7, n^n\equiv 2^n…
Chon
  • 6,002
6
votes
4 answers

$a^m + b^n \equiv 1 \mod ab$ for some $m,n$

If $a$ and $b$ are relatively prime integers, then there exist integers $m$ and $n$ such that $a^m + b^n \equiv 1 \mod ab$ . How do I show this to be true? (Artin's Algebra problem 11.1.16)
Paul Orland
  • 6,888