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

If $ x \not\equiv 0, 4 \pmod{8} $, how can I prove that $ x^2 \equiv k^2 \pmod{16} \iff x \equiv \pm k \pmod{8} $?

Let $ k $ be a positive integer. Let x be a positive integer that satisfies $ x \not\equiv 0 \pmod{8} $ and $ x \not\equiv 4 \pmod{8} $. Then is the following statement true? $$ x^2 \equiv k^2 \pmod{16} \iff x \equiv \pm k \pmod{8}. $$ Example: Let…
Lone Learner
  • 1,076
0
votes
2 answers

Solving linear congruences - Number Thoery

I am having some trouble getting the correct answer on linear congruences. Any help would be appreciated! Consider the following: Solve $25x = 15 $ (mod 29) The gdc(25,29) = 1. Therefore, x has one solution. Using the extended Euclidean algorithm we…
mont
  • 33
0
votes
0 answers

Modulo of an arithmetic expression

I have a bucket of elements, the amount of elements $E$ is given by this equation, with constraints on parameters $S_A$ and $S_B$: $$ \begin{equation*} \left\{ \begin{alignedat}{3} E_0 = (4-S_{A}) + 4*N + S_{B} \\ S_{A} < 4 ; S_{A} \in N\\ …
Fra93
  • 161
0
votes
1 answer

How to find all solutions for $12x \equiv 12 \pmod {30}$?

How to find all solutions for $12x \equiv 12 \pmod{30}$ ? $12x \equiv 12 \pmod{30}$ gives $12x=12+30y$ $\gcd(30,12)=6$ $30=2\cdot12+6$ $12=2\cdot6$ $6=30-(2*12)$ Multiply all with 2: $12=2\cdot30-4\cdot12$ Switch sides for easier…
Bioelli
  • 183
0
votes
0 answers

Iterated modulus of the form $n-(n \bmod k)$

I have a recursion formula $f_{n,k}(0)=n$ and $f_{n,k}(i)=n-f_{n,k}(i-1)\bmod k$ where $n,k$ are positive integers and $k
Jfischer
  • 1,239
0
votes
1 answer

Two sequences of integer numbers an and bn satisfy the following conditions:

Two sequences of integer numbers $a_n$ and $b_n$ satisfy the following conditions: $$a_1=1$$ $$b_1=2$$ $$a_{n+1} ≡ 5a_n + 1 \ (\text{mod}\ 2022)$$ $$b_{n+1} ≡ 5b_n + 1 \ (\text{mod}\ 2022)$$ for all integer n ≥ 1. Show that for all $n ∈ Z^+$, $$a_n…
user1093595
0
votes
0 answers

How to solve $x \bmod y = z$?

I'm working on a cryptography programming puzzle. I've worked out that the basic formula to generate a character is $$(x \cdot 2^i)\bmod 67 = character.$$ In order to decode, I need to work out what are the possible values for x, with $1 \leq x \leq…
0
votes
0 answers

Why the modular arithmetic requires modulus to be an integer greater than one?

The modular arithmetic article in Wikipedia tells that the modulus in modular arithmetic should be an integer greater than $1$. But I can easily imagine a similar algebra where equivalence classes are defined as $a\equiv a+n$ or $a\equiv a+n/2$, for…
Anixx
  • 9,119
0
votes
0 answers

Determine all k ∈ N such that $n^{k}$ ≡ n (mod 7) for all integers n.

How would I prove this statement? This is what I have tried, but it seems to be incorrect: writing the congruence as 7 | n(1-$n^{k-1}$) then, either 7 | n or 7 | 1-$n^{k-1}$, none of which cannot be true for all n regardless of the k value I'm not…
user
  • 21
0
votes
0 answers

Congruent modulo n

Given a natural number n, and two integers a and b. Show that if: a)a ≡ b and b≡c, it follows that a≡c b)a≡b and c≡d, it follows that a+c≡b+d and ac≡bd c)that a≡b if and only if a and b give the same remainder when divided by n *I solved a) by…
0
votes
0 answers

Why is this congruence modulo m true?

Some Background This is from a proof of the existence of inverses modulo m. Briefly written... Let $a, m \in \mathbb{Z}$. Assume $\gcd(a,m)=1$. By Bezout, $\gcd(a,m)=as+mt=1$ for some $s, t \in \mathbb{Z}$. Taking$\mod m$ we get $$ \begin{align} 1 &…
user1077997
0
votes
0 answers

Question on properties of congruence mod $n$

I know it is true that, if for example, $a \equiv b \equiv 1 \bmod 2$, then $$a^3 + ab^2 + b^3 \equiv 1^3 + 1 \cdot 1^2 + 1^3 \equiv 1 \bmod 2.$$ (I hope this notation is fine, but if not, someone please correct me.) I'm trying to understand exactly…
Cardinality
  • 1,097
  • 3
  • 7
0
votes
1 answer

Given $245^2\equiv 1\pmod{2501}$. Find $x,y$ such that $x\cdot y=2501$.

Given $245^2\equiv 1\pmod{2501}$ Find $x,y$ such that $x\cdot y=2501$. (obviously not $x=1,y=2501$) How am I suppose to approach this problem ? I don't know how to start, can't see how the given helps me to find $x,y$. Help please, thanks !
Algo
  • 2,322
0
votes
3 answers

What is the proof for this question regarding subtraction in modular arithmetic?

Numbers that are 1 mod 4 can be categorised into two categories. A) The first category is numbers that are 1 mod 4 but not 1 mod 8. I will list some of them here:5,13,21,29,37 e.t.c B)The second category is numbers that are 1 mod 8. for example:…
0
votes
0 answers

periodicity question for $2^n \bmod 10^d$

I'm trying to find a cleaner formula for various powers-of-10 residuals for any power of 2 e.g. 2^x last 14-digits delta ----------------------------------------------------------- 24 = 16777216 =…