New answers tagged

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)$ ...
DrDoofenshmirtz's user avatar
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^...
Arturo Magidin's user avatar
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)$.
Greg Martin's user avatar
  • 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 $\...
Esgeriath's user avatar
  • 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(...
Ilikemath's user avatar
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 ...
DonAntonio's user avatar
  • 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)$ ...
Mario Falciatore's user avatar
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 (...
Bill Dubuque's user avatar
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 ...
Calvin Lin's user avatar
  • 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 ...
Malady's user avatar
  • 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&...
Oscar Lanzi's user avatar
  • 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$$
jjagmath's user avatar
  • 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 ...
Nothing special's user avatar
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 ...
Nothing special's user avatar
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)$.
gbohus's user avatar
  • 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 ...
Thomas Andrews's user avatar
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 $$ ...
Will Jagy's user avatar
  • 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 \...
jjagmath's user avatar
  • 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\\ &=...
kelalaka's user avatar
  • 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^{\...
Thomas Ahle's user avatar
  • 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 =...
Yathiraj Sharma's user avatar
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 + (...
Tzimmo's user avatar
  • 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^...
BBBBBB's user avatar
  • 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$ ...
John Omielan's user avatar
  • 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 ...
Mastrem's user avatar
  • 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 ...
dan_fulea's user avatar
  • 31.5k

Top 50 recent answers are included