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$.

6
votes
1answer
84 views

Show that a following equation has no solution in integers: $x^3-x+9=5y^2$

Show that a following equation has no solution in integers: $$x^3-x+9=5y^2$$ Clearly we see that $y$ is odd, so $y^2\equiv_8 1$ and thus $8\mid x^3-x-4$. So if $x$ is odd, then $x-1$ and $x+1$ one is ...
1
vote
2answers
152 views

Congruence using extended GCD

$$\eqalign{ x &\equiv 5 \mod 15\cr x &\equiv 8 \mod 21\cr}$$ The extended Euclidean algorithm gives $x≡50 \bmod 105$. I understand now that if we combine the two it implies $...
0
votes
2answers
124 views

Chinese Remainder Theorem example

$$x = 4 \bmod 18$$ $$x = 52 \bmod 96$$ $$x = 6 \bmod 20$$ My current algorithm thinks the answer is $x \equiv 1066 \bmod 1440$ but I don't think there should be a solution to this. The algorithm: ...
4
votes
3answers
165 views

Solve $x^2\equiv -3\pmod {\!91}$ by CRT lifting roots $\!\bmod 13\ \&\ 7$

Question 1) Solve $$x^2\equiv -3\pmod {13}$$ I see that $x^2+3=13n$. I don't really know what to do? Any hints? The solution should be $$x\equiv \pm 6 \pmod {13}$$ Question 2) $\ $ [note $\bmod 7\!:...
2
votes
0answers
54 views

Sequence of positive integers $n$ such that $n^2+n+1$ divides $4^n+2^n+1$ and $n$ is not power two

Source problem from this post. We have two term of sequence: 215,3692374808. Let $m=n^2+n+1$. For both first terms $m$ is prime. Question 1: can be $m$ is not ...
1
vote
0answers
57 views

Collatz conjecture, Tao-Collatz remainder and mod n.

Collatz conjecture is equivalent to $n\times 3^{k} = 2^{ak+1} - TCR$ where, for me, $k$=odd steps, and $ak+1 $=even steps. Note that total steps = k +( ak+1) steps. Some numbers have the same total ...
0
votes
1answer
36 views

How to calculate 'n' given basic operations like '(n + x) mod p = r' where 'x', 'p', and 'r' are known?

Is it possible to calculate n for a given x, p, r in different scenarios with basic operations such as ...
1
vote
2answers
823 views

Solving equation with mod and one variable

I've marked this up the best way I can: $0 \equiv (19+16x) \pmod{15-x}$ I can repeat this equation filling in $x$, which gets increased by one with each pass. When you get to $x$ = 8, the remainder ...
3
votes
1answer
86 views

Computing $\sum_{k=1}^n (a^k \bmod m)$

I would like to find a closed form solution for $$\sum_{k=1}^n (a^k \bmod m)$$ $$0<a<m, n > 0$$ Note that the mod operator is within the brackets. If a closed form solution does not exist, ...
0
votes
1answer
89 views

Found $a^2\equiv b^2(\mod RSA\_1024)$ What are the chances?

Due to the size of the numbers, I am writing them as a code. Below are $a$ and $b$ ...
2
votes
1answer
61 views

Solutions mod p of the equation $x^4-17=2y^2$

I'm trying to prove that for every $p$ there are solutions $\pmod{p}$ for this equation. I've tried to follow this answer: Show that the congruence $x^4 - 17y^4 \equiv 2z^2 \pmod p$ has non-trivial ...
3
votes
3answers
57 views

What is the motivation behind defining congruence / residue classes?

I mean instead of partitioning $\mathbb Z$ to $n$ different sets named residue classes and defining arithmetic operations on them, we can just define $$\mathbb Z_n = \lbrace 0, 1, 2, ..., n-1 \...
1
vote
3answers
48 views

Solutions to $a^2\equiv 1\mod 2^k$

I apologize in advanced as my literacy in this subject is not too great and this question may either be trivial or impossible as of yet. I have seen many questions on stack exchange utilizing the ...
0
votes
1answer
59 views

Modular Arithmetic: Congruence System [on hold]

How to solve this congruence system: \begin{cases} x≡2 &\bmod3 \\ 2x≡1& \bmod5 \\ 3x≡3 &\bmod6 \end{cases}
2
votes
3answers
76 views

If $x^3$ is a square, is $x$ a square?

Very simple question here, which I feel like I should be able to answer but am struggling with. Let $k$ be a finite field, and let $x\in k^\times$. Is it true that $$x^3\in\left(k^\times\right)^2 \...
0
votes
2answers
46 views

Solutions of $x^2 \equiv 1 \pmod N$

I am stuck with this exercise: Show that $\forall s >0 \quad \exists N >0$ such that $$x^2 \equiv 1\pmod N$$ has more than $s$ solutions. I think I cannot use the theory if quadratic ...
-1
votes
3answers
121 views

Why does 3x ≡ -29 (mod 5) equal to 3x ≡ 1 (mod 5)

I'm having some trouble understanding the following problem, why can you write the following congruence: $$3x ≡ -29 \pmod{5} $$ as $$3x ≡ 1\pmod{5} $$
0
votes
3answers
33 views

Solving a congruence with Chinese Remainder Theorem

I need help solving a congruence with the help of Chinese Remainder Theorem. I am not sure how I could get 3 congruences out of one. For solving congruences I use Euclid's algorithm. Here's an example:...
2
votes
1answer
33 views

$\forall p \ge 11 \quad \exists n \in \{1,2,\dots,9\}$ such that $n$ and $n+1$ are quadratic residues mod p

I must solve the following problem: $\forall p \ge 11 \quad \exists n \in \{1,2,\dots,9\}$ such that $n$ and $n+1$ are quadratic residues mod $p$. I read some questions here about this topic but I ...
0
votes
0answers
26 views

Find a non-trivial polynomial which has all integers as zeros mod p

This is an exercise from the book "Einführung in die algebraische Zahlentheorie" by Alexander Schmidt. Let p be a prime number. And let $f \in \mathbb{Z}[X]$ be a polynomial with integer coefficients ...
1
vote
1answer
696 views

Prove that the order of $5$ mod $2^k$ is equal to $2^{k-2}$ where k is any integer greater than or equal to 3.

Here is a proof: Prove that $\text{ord}_{2^k}5=2^{k-2}$ where $k$ is any integer $\geq3$ I do understand that $n_k$ is odd but how does that relate to the order of 5 mod $2^k$? Why does that show ...
1
vote
2answers
34 views

How does one prove that $1 + a + a^2 + … +a^{\phi(n)-1} = 0$ mod $n$ if $a$ and $a-1$ are both units mod n?

If a has order $\phi(n)$, then this is easy, because (if n>=3) all units arise in pairs a and n-a. However, the two conditions a and a-1 units do NOT imply that the order of a is $\phi(n)$, so we ...
0
votes
2answers
39 views

How to solve congruence with two variables x and y

I'm having trouble solving the following congruence: $$2x + 2y ≡ 0 \pmod{7}.$$ What I've tried so far is writing the congruence as follows: since the remainder is $0,$ we know $7$ is divisible by $...
1
vote
0answers
21 views

Solving equations with mod 1 numbers and multiple variables

I have two numbers (inputs): $ca$ and $cb$ and an expected result (output): $cc$. All of those are $mod 1$ numbers, usually represented as fractions like $\frac ab$ where $a$ and $b$ are integers, e.g....
1
vote
1answer
103 views

How to prove that $\lim\limits_{n\rightarrow \infty} \frac{1}{n^2}\sum\limits_{k=1}^{n}(n \bmod k)=1-\frac{\pi^2}{12}$?

I learnt that $$\lim_{n\rightarrow \infty} \frac{1}{n^2}\sum_{k=1}^{n}(n \bmod k)=1-\frac{\pi^2}{12}$$ where $ (n{\bmod {k}})$ is the remainder upon division of $n$ by $k$. However, I am not sure ...
2
votes
2answers
35 views

Question about congruence operations and multiple variables

My question is somewhat related to this thread: How to solve congruence with two variables x and y I can not post a comment to ask directly there, therefore I need to create this thread Anyhow, as ...
1
vote
1answer
36 views

How to solve Chinese Remainder Theorem with exponantial values

I need help solving this Chinese Remainder Theorem, but I would like to solve it using Euclid's Algorithm. \begin{align*} 2x &\equiv 4^{2010} \pmod{3} \\ 15x &\equiv 13 \pmod{4} \\ 3x &...
1
vote
3answers
922 views

How to use Fermat's little theorem to find $50^{50}\pmod{13}$?

I don't understand how to use Fermat's little theorem to find remainders e.g if we are asked to find remainder of $50^{50}$ on division by $13$, what is a and what is $p$ in the formula? Also I ...
0
votes
1answer
43 views

Prove there exists $a$ such that $a^\frac{n-1}{2} \neq (\frac{a}{n}) (\text{mod } n)$

I want to prove the following proposition: Let $n=pq$ where $p,q$ are odd primes; Prove there exists a number $a \in \mathbb{Z}_n^x$ such that $a^\frac{n-1}{2} \neq (\frac{a}{n}) (\text{mod } n)$ ...
0
votes
2answers
1k views

Binary modulo operation

Empirically, I can know that (a+b+c) mod 2 = (a-b-c) mod 2. e.g.,) 1+2+3 = 6, 6 mod 2 = 0 1-2-3 = -4, -4 mod 2 = 0 1+2+4 = 7, 7 mod 2 = 1 1-2-4 = -5, -5 mod 2 = 1 It seems that it ...
0
votes
2answers
45 views

Modular arithmetic of numbers

let us consider two integers a,b that are co prime to a prime number p Then is there any relation between a%p, b%p and ab%p ? % = modulo operator
-2
votes
2answers
48 views

When does $n-2$ divide $n-5$? [on hold]

We got asked this question today in a national exam: $n$ is a positive integer; find the values of $n$ for which $n-2$ divides $n-5$.
-1
votes
1answer
37 views

How to solve congruence using diophantine equation?

Id like to know how to solve this congruence, 2x + 5y ≡ 0(mod 7)so far i've tried solving it like a Diophantine equation which gave me ...
0
votes
2answers
30 views

Idempotent elements in a modulo n ring

I'm trying to find the idempotent elements of the ring ($\Bbb Z_{36} $, +, $ \cdot $) so I "split" it into $ \operatorname{Idemp}(\Bbb Z_4 \times \Bbb Z_9) $, meaning $\operatorname{Idemp}(\Bbb Z_4) \...
0
votes
1answer
44 views

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$ (...
10
votes
4answers
192 views

Trig identities analogous to $\tan(\pi/5)+4\sin(\pi/5)=\sqrt{5+2\sqrt{5}}$

The following trig identities have shown up in various questions on MSE: $$-\tan\frac{\pi}{5}+4\sin\frac{2\pi}{5}=\tan\frac{\pi}{5}+4\sin\frac{\pi}{5}=\sqrt{5+2\sqrt{5}}$$ $$-\tan\frac{2\pi}{7}+4\sin\...
1
vote
1answer
27 views

$x^2 + 4x - \lambda +2 \equiv 0 \pmod 7$

I solved this problem but I don't know if my solution is right: Find the values of $\lambda, 0 \le \lambda \le 6$, such that the congruence $x^2 + 4x - \lambda +2 \equiv 0 \pmod 7$ has a ...
1
vote
1answer
39 views

Solution to linear equation system using modulo 251?

I'm trying to solve the following linear equation system using modular arithmetic with modulo 251. I know it can also be resolved using Gauss Jordan but I'm not sure how to do it applying modulo 251 ...
1
vote
1answer
51 views

When exactly is N (mod ab) the same as N (mod a)? (2010 AMC 10A Q24)

This question stems from 2010 AMC 10A, Q24 solution given at AOPS. If I understand right, we have a number N divisible by 4, but not by 25. And it is argued that since 'N mod 4 = 0', N mod 100 = N ...
1
vote
2answers
385 views

Congruent iff Same Remainder (CISR) Confusion

I was reading through a proof of the following proposition: $$a\equiv b\!\!\pmod{m}\iff (a\bmod m) = (b\bmod m)$$ i.e. $\ a \equiv b \pmod{\!m} $ if and only if a and b leave the same remainder when ...
1
vote
1answer
48 views

Minimal integer to make a rational into an integer

Let $q = \frac ab$ be any rational number such that $a < b$. What is the smallest positive integer $n$ such that $\frac ab \times \left(2^n-1\right)$ is an integer?
-2
votes
1answer
28 views

sum of all the pairs for (A[i]%B[j]) in a given array [on hold]

Given an array find the total sum of all the pairs over (A[i]%B[j]). % => mod Eg: [1,2,3] Ans: 5 Explaniation: 1%1 = 0 1%2 = 1 1%3 = 1 2%1 = 0 2%2 = 0 2%3 = 2 3%1 = 0 3%2 = 1 3%3 = 0 total sum is ...
5
votes
0answers
68 views

Can long numbers be “3-palindromic”?

Question Let $n$ be a number with $d\ge9$ digits when written in number base $b\ge2$. Can $n$ be $3$-palindromic? That is, does there exist $b$, such that $n$ is simultaneously a ...
3
votes
3answers
167 views

Modular Arithmetic in AMC 2010 10A #24

Link to the problem/solution: https://artofproblemsolving.com/wiki/index.php/2010_AMC_10A_Problems/Problem_24 I'm trying to understand the following step in the solution to the aforementioned AMC ...
1
vote
1answer
40 views

How to show that $\sum \limits_{ \{x_1,x_2, \cdots , x_k \} \in S} \prod\limits_{i=1}^{k} x_i \equiv 0\ (\text {mod}\ p).$

Let $p$ be an odd prime. For each $1 \leq k \leq p-2$ consider the sets $S$ of all $k$-subsets of $\{1,2, \cdots, p-1 \}.$ Show that $$\sum \limits_{ \{x_1,x_2, \cdots , x_k \} \in S} \prod\limits_{i=...
2
votes
2answers
66 views

can we perform modulo operator on a fraction on both of it's numerator and denominator?

I want to calculate nCr (mod $10^9+1)$.so for calculating nCr we have: $$nCr=\frac{n!}{r!(n-r)!}$$ so I want to know whether it is true that I perform modulo operator to numerator and denominator ...
1
vote
0answers
27 views

Examples of recurrences on the infinite binary tree?

Given a infinite binary tree rooted at node 1 where children of node $i$ are $2i$ and $2i+1$, with each node having a value $v(i)$. The values of the first $k$ nodes are given, the value of any node ...
0
votes
2answers
65 views

without actually finding them, determine the number of solutions of the congruence.

without actually finding then, determine the number of solutions of the congruence. $$x ^2 \equiv 3 \pmod {11^2 . 23^2}$$ My professor gave a hint of finding the order of the group of units and the ...
1
vote
0answers
20 views

Validate my proof of $U(n) = \lbrace k : (k, n) = 1 \space and \space 0 < k < n \rbrace$ is closed under modular multiplication

Let $A, B \in U(n)$ for any $n \in \mathbb N^+$. Then we need to show that (ordinary) multiplication of $A, B$ ($AB$) satisfies the following, $$(AB, n) = 1$$ Which is can be done using the Bézout's ...
0
votes
0answers
30 views

Prime is in P: Prove that $(X+a)^{\frac{n}{p}} \equiv X^{\frac{n}{p}} +a \mod(X^r -1, p)$ for $1\leq a\leq \lfloor \log n\sqrt\phi(r)\rfloor $

For the problem we have $r<p$, p prime such that $p\mid n$, $O_r(n)>\log^2n $, $O_r(p)>1$. Also, we have as premises that for $1\leq a\leq \lfloor \log n\sqrt\phi(r)\rfloor $: 1) $(X+a)^{n} ...