New answers tagged modular-arithmetic
1
vote
Prove that if $e.d \equiv 1 \bmod (p-1)(q-1)$ then it’s impossible to have $e.d \equiv 1 \bmod pq$
The statement you have given appears to be false. A counterexample which first strung to my mind is $e = 31$ and $d = 27791$. Taking $p = 89, q = 11$, we get $e*d$ congruent to both $1$ mod $(p*q)$ ...
1
vote
relation between exponentials in modulus operation
Note that $k$ is a generator if and only if its multiplicative order modulo $97$ is $96$.
Since $5$ is a primitive root modulo $97$, it has multiplicative order $96$, as does $k$. But the order of $k^...
- 388k
1
vote
Accepted
How could you write mod(a, x) with complex numbers?
One can simply use the identity
$$
\text{mod}(x,a) = a\text{ mod}(\tfrac xa,1)
$$
to convert the formula in the OP into a formula for mod$(x,a)$.
- 75.2k
0
votes
$| \{a \in \mathbb{Z}_{24} : a^{1001} = [5]\} |=?$
The comment under the question already provides an answer, but let me give another.
Notice that $\gcd(5, 24) = 1$, so $5$ has multiplicative inverse modulo $24$.
On the other hand, any $a$ such that $\...
- 1,970
1
vote
If f(n) is congruent to r(mod m), is f(km + n) congruent to r(mod m)?
My simple proof,
Proof: Let $f(x)=c_0+c_1x+c_2x^2+ \cdots +c_dx^d$.
We see that from binomial expansion $(km+n)^t\equiv a^t\bmod m.$
Therefore $f(km+n)=a_0+c_1(km+n)+c_2(km+n)^2+\cdots+c_d(km+n)^d$
$f(...
- 87
0
votes
Using Euler's totient theorem to compute $11^{-1}$ mod $26$
When the numbers are fairly small one can take advantage of a some basic arithmetic.
Since $\;11\cdot7=77=-1\pmod{26}\;$, because $\;26\cdot3=78\;$ , we get:
$$11\cdot(-7)=1\pmod {26}\,,\,\text{and ...
- 210k
0
votes
For $d \in \mathbb{Z}^+$ $x^d-1 \equiv 0 \pmod{p}$ has $p-1$ solutions iff $p-1\mid d$
By Fermat little theorem, for all non zero $x \in \mathbb{Z}/p\mathbb{Z}$ (they are $p-1$) we have
$$x^{p-1} \equiv 1$$
In other world we have $p-1$ solution.
So if $d|p-1$ we have $d=\alpha(p-1)$ ...
- 556
0
votes
Chinese remainder theorem method
The accepted answer does not explictly address an important point: $ $ the $\rm\color{#0a0}{ necessity\ (\Rightarrow})\:\!$ and $\rm\color{#c00}{sufficiency\ (\Leftarrow)}\!\:$ of the CRT solutions (...
- 269k
1
vote
Accepted
Characterizing numbers satisfying simple covering property
Observations towards a solution. If you're stuck, explain what you've tried.
Step 1: Assume that $A+B = C+D$. Show that there is an intersection iff $ B+C > A+B$.
Like OP mentioned, it is ...
- 66.8k
1
vote
Modulo question solving for x
You’ve tried using Fermat’s Little Theorem, ie. $a^{p-1}=1 \mod p$ for all primes $p$ and all integers $a$. Let us proceed along these lines. This tells us that $39^{100}=1 \mod 101$. This says that ...
- 737
0
votes
Does this pattern for the order of $2$ modulo a power of a prime always hold?
With base $10$ instead of $2$ the corresponding minimal counterexample is $p=487$, thus $10^{486}-1$ is divisible by $487^2$.
This has implications for a famous puzzle, the "twin square problem&...
- 37.7k
10
votes
Accepted
Does this pattern for the order of $2$ modulo a power of a prime always hold?
No:
$$\text{ord}_{1093}(2)=\text{ord}_{1093^2}(2)=364$$
- 17.2k
0
votes
How to find the inverse modulo $m$?
$$7x\equiv 1\pmod{31}$$
We are seeking integer solutions of the equation,
$$7x+31y=1$$
Find a linear transformation $\begin{pmatrix}\cdot & \cdot \\ \cdot &\cdot\end{pmatrix}$ consisting of ...
- 1,300
0
votes
$2017^{2016^{2015}} \mod 1000$
Claim: If $x$ is relatively prime to $1000$,
$x^{100}\equiv 1\pmod{1000}$.
Proof:
Consider the group of units/totatives of $1000$ under multiplication modulo $1000$.
By direct product decomposition ...
- 1,300
1
vote
Square root of 1 modulo N
In @WhatsUp's analysis the case of $p = 2$ has a small error for $r \ge 3$. It is true that there are four roots, but they are $1$, $(2^{r-1} - 1)$, $(2^{r-1}+1)$ and $(2^r - 1)$.
- 11
4
votes
Accepted
Sum of squares $\pmod p$
If $p$ is an odd prime, the non-zero squares are exactly the roots of $x^{(p-1)/2}-1,$ and so, when $(p-1)/2>1,$ the sum of the roots is zero. Your sum is twice the sum.
More generally, if $j$ is ...
- 176k
1
vote
Experimentally found weird number theory pattern $p^\frac{d-3}{2}\cdot \left(p^\frac{d-1}2 \pm \{-1 \text{ or } p-1 \}\right) \mod d$ equals $0,1$
Using commas for an ordered list and $(p|q)$ for Legendre symbol. After multiplying through by $p$ I get the question to be
$$ 1 + (p|q) (p-1, -1, 1-p,1 ) \equiv \; \; (?,?,?,?) \pmod d $$
...
- 138k
3
votes
Accepted
Experimentally found weird number theory pattern $p^\frac{d-3}{2}\cdot \left(p^\frac{d-1}2 \pm \{-1 \text{ or } p-1 \}\right) \mod d$ equals $0,1$
Your conjecture follows from the Euler's criterion: If $p$ is a prime and $(a,p) = 1$, then $$a^{\tfrac{p-1}{2}}\equiv
\begin{cases}
1 \pmod p&\text{if $a$ is a quadratic residue $\bmod p$}\\
-1 \...
- 17.2k
2
votes
Accepted
Show that this RSA encryption iterated $10$ times does not encrypt $x$
Let we have RSA encrypt $E(x) = x^{49} \bmod 215629$ then the double RSA encrypt is
\begin{align}
E^2(x) &= (x^{49})^{49} \bmod 215629\\
&= \color{red}{x^{49\cdot49}} \bmod 215629\\
&=...
- 1,629
0
votes
Another Binomial Coefficient Congruence Modulo Prime Powers
Theorem 1:
Let $ p $ be a prime and let $ s $ and $\ell$ be positive integers.
For any integers $n$, and $k$, such that $k < p^{\ell}$,
write $n=n_1 p^{\ell+s-1} + n_0$ where $ 0 \leq n_0 < p^{\...
- 4,512
1
vote
Looking for a better proof in $\mathbb{Z}/11\mathbb{Z}$
Partial Hint: Check when 0 can be expressed as sum of two quadratic residues.
For instance: In case of $p=13$, see that $-1$ is a quadratic residue (since $-1\equiv 5^2 \pmod {13}$). Hence,
$$5^2+1^2 =...
- 1,478
2
votes
Looking for a better proof in $\mathbb{Z}/11\mathbb{Z}$
Considering $n=2$ is enough to show that there are no solutions for even $n$. Suppose that we know there are no non-trivial solutions for $n = 2$.
If $n = 2k$ and $x^n + y^n = 0$, you get $(x^k)^2 + (...
- 950
1
vote
Probability of random $n \times n$ matrix in $\mathbb{Z}_q$ being invertible?
Assuming that all your entries are being chosen uniformly at random, note first that there are $q^{n^2}$ total matrices over $\mathbb F_q$, and according to this post there are
$$\prod_{i=0}^{n-1} (q^...
- 1,012
1
vote
Find all positive integers m so that for $n=4m (2^m - 1)$, $n | (a^m - 1)$ for all a coprime to n
As you've done, have
$$m = 2^{q}r \tag{1}\label{eq1A}$$
with $r$ being odd. Regarding your first congruence equation, i.e.,
$$a^{m} \equiv 1 \pmod{2^{q+2}} \tag{2}\label{eq2A}$$
note that $q = 0$ ...
- 46.6k
0
votes
Prove that there exists $1\leq a < p^{1/(2\sqrt{e})} (\log p)^2$ that is a quadratic non-residue modulo p
Since no-one else has answered, I wil give you the strongest result I can. It can probably be strengthened by considering the speed of convergence in Mertens second theorem, but I don't have the time ...
- 8,154
1
vote
What is the remainder when dividing $a$ by $5$ if $\sum_{k=1}^{1992}\frac{1}{k}=\frac{a}{b}$?
Let $S=S_{1992}=\frac ab$ be the given rational number, written as an irreducible fraction. The only way to proceed is to find $b$ exactly first.
(I could not see any Wolstenholme-type theorems that ...
- 31.5k
Top 50 recent answers are included