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

9,304 questions
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 ...
152 views

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 ...
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 ...
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 ...
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 ...
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, ...
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$ ...
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 ...
57 views

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 ...
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}$$
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:...
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 ...
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 ...
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 ...
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 ...
39 views

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$ (...
192 views

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