Skip to main content

New answers tagged

3 votes
Accepted

Show $x^p-x$ is not in $\ker\Psi_p$

It is obviously not in the kernel by looking at the coefficients of the polynomial. To prove that all evaluations are $0$, use Lagrange's theorem for the multiplicative group of the field of $p$ ...
Bennie's user avatar
  • 183
0 votes
Accepted

Last two digits of a sequence

This is about sequences of powers modulo $100$. We may check that the order of $23 \:(\text{mod }100)$ is $20$. The values of $23^n \:(\text{mod }100)$ for $n = 1$ to $20$ are: $$23, 29, 67, 41, 43, ...
Sputnik's user avatar
  • 3,857
0 votes

Last two digits of a sequence

First thing to realise, is that the last digit is repeated after four times, as you can see in the following table: $a$ $a^2$ $a^3$ $a^4$ $a^5$ $1$ $1$ $1$ $1$ $1$ $2$ $4$ $8$ $6$ $2$ $3$ $9$ $7$ $...
Dominique's user avatar
  • 2,625
1 vote

How to check for solutions of non-linear systems over the integers modulo m?

Let's see, lemma, given a prime $p$ and a target $t,$ there always exist $x,y$ such that $x^2 + y^2 \equiv t \pmod p.$ This one uses just a counting/pigeonhole argument This can always be done for ...
Will Jagy's user avatar
  • 141k
1 vote
Accepted

Natural way to extend the ring $\mathbb{Z} / p^k \mathbb{Z}$ so that the equation $x^2 + 1 \equiv 0 (\text{mod }p^k)$ has a solution

A simple way to define your ring is to start with the ring of Gaussian integers and take the congruence modulo $p^k$ on this ring. Or directly, consider the set $$ R = \bigl\{x + iy \mid x, y \in {\...
J.-E. Pin's user avatar
  • 40.7k
1 vote
Accepted

Simplifying a reciprocal of a product of two quadratics using modular arithmetic

The sum equals … $5$, independent of $q$! (Of course we must have $q\equiv1\pmod5$ for such a $k$ to exist.) Evidence first, then a proof. Evidence: Calculating it by brute force for $q=11,31,41,61,...
Greg Martin's user avatar
2 votes

Finding BCH code syndromes

The question matches the changes I made to my test code: $GF(2^4):1 + x^3 + x^4$, $m_1 m_3 = 1 + x + x^2 + x^4 + x^8$, $v(x) = x^2 + x^5 + x^8 + x^{11} + x^{14}$ I'm not aware of calculating syndromes ...
rcgldr's user avatar
  • 596
0 votes

Factors of a quadratic in modulo $9$

Write the equation as $$(x+b)^2 = b^2-1$$ with $b = \frac{a}{2}$. Now the ring $\mathbb{Z}/9$ has the property that any square of the form $b^2-1$ is $0$. We get $(x+b)^2=0$, which has $3$ solutions. ...
orangeskid's user avatar
  • 54.9k
3 votes
Accepted

Show that $11^{n+2}+12^{2n+1}$ is divisible by 133 for any natural 'n'.

Observe $12^{2n+1} = 12 \cdot (12^2)^n \equiv 12 \cdot 11^n \pmod{133}$, since $12^2 = 144 \equiv 11 \pmod{133}$. So $11^{n+2} + 12^{2n+1} \equiv 11^{n+2} + 12 \cdot 11^n = 11^n(11^2 + 12) = 11^n \...
Martin Westin's user avatar
1 vote

Factors of a quadratic in modulo $9$

Assume that $$f(x)\equiv (x-b)(x-c)\pmod9.$$ You already observed that $bc\equiv1\pmod9$, so also $bc\equiv1\pmod3$. It follows that $b$ and $c$ must congruent to each other modulo three. For ...
Jyrki Lahtonen's user avatar
1 vote

How to prove that all elements inside a cycle of a cyclic group are different from each other

Here is the standard way to see this. Suppose that $n = ord(a)$, so $n$ is the smallest positive integer such that $a^n = e$. Then note the following: (*) $a^k = e$ if and only if $n$ divides $k$. ...
testaccount's user avatar
  • 1,033
0 votes

Find All Solutions to System of Congruence

You did it well until the computation of $x$. You forgot to do the multiplication by $3$ in the last term: $$x=(-20*1)*2-(15*1)*1+(12*3)*3\equiv 53\pmod{60} $$
Bob Dobbs's user avatar
  • 11.8k
1 vote

Factors of a quadratic in modulo $9$

All congruences in this answer are modulo $9$. Completing the square, $x^2+ax+1\equiv0\iff\left(x+\frac a2\right)^2\equiv\frac{a^2}4-1\iff(2x+a)^2\equiv a^2-4$. Squares are $0^2\equiv0, (\pm1)^2\...
J. W. Tanner's user avatar
  • 61.5k
1 vote

Factors of a quadratic in modulo $9$

Key Idea $\!\!$ if $f(x)$ has a root $\,x\equiv \color{0}b \pmod {\!p^2}\:\!$ that's $\rm\color{#c00}{repeated}$ $\!\bmod{p},\,$ i.e. $\,\color{#c00}{f'(b)\equiv 0}\pmod{\!p},\,$ then it lifts to $\,p\...
Bill Dubuque's user avatar
1 vote
Accepted

Why is the order of an element equal to the order of the group it generates?

Suppose that $ord(a) = n$ for some integer $n > 0$. Then $a^n =e$. Thus $a \circ a^{n-1} = e$, and multiplying both sides with $a^{-1}$ gives you $$a^{-1} = a^{n-1}.$$ Now raising both powers by ...
testaccount's user avatar
  • 1,033
1 vote

Question involving Fermat's Little Theorem

What you are doing wrong is applying Fermat’s Little Theorem to $m=2p$, which is not prime. For composites, you should use Euler’s theorem.
J. W. Tanner's user avatar
  • 61.5k
1 vote

Question involving Fermat's Little Theorem

As mentioned in the comment, Fermat's little only applies to primes. Since $p$ and $2$ are coprime, it suffices to show $2\mid 2^{2p-1}-2$ (which is obvious as both of $2^{2p-1}$ and $2$ are even), ...
Just a user's user avatar
  • 17.8k
1 vote

If $d\mid10a-1$ then $d\mid10q+r\iff d\mid q+ar$

$d\mid10a-1\;.$ Prove that $\;d\mid10q+r\iff d\mid q+ar\;.$ Proof$\,\implies:$ Since $\;d\mid10a-1\,,\;$ it follows that $\;d\mid r(10a-1)\;.$ Since $\;d\mid r(10a-1)\;$ and $\;d\mid 10q+r\;,\;$ we ...
Angelo's user avatar
  • 12.4k
0 votes

If $d\mid10a-1$ then $d\mid10q+r\iff d\mid q+ar$

Given that, $d \mid (10a -1)$. Now as you have shown, $d \mid 10aq + ar$ so $d \mid (10aq + ar) - q(10a -1) \implies d \mid q + ar$ If $d \mid (q + ar)$ then $d \mid 10(q+ar) - r(10a -1) \implies d \...
Afntu's user avatar
  • 2,217
10 votes
Accepted

Is $\sqrt{2}$ an element of the set $\{k \bmod 2\pi \mid k \in \mathbb{N}\}$?

$\pi$ is a transcendental number, meaning it is not the solution of any non-trivial polynomial with integer coefficients. If we had $\sqrt{2} = k-2n\pi$ then this would imply that $(k-2n\pi)^2-2=0$, ...
Daniel Czmmx's user avatar
2 votes

How can I convert Interval Difference to Circle of Fifths segments and position

If I understand your system correctly, your numbers are just the 12-ET frequency ratio relative to C, i.e., C = $1$ C♯/D♭ = $2^{1/12} \approx 1.059$ D = $2^{1/6} \approx 1.122$ D♯/E♭ = $2^{1/4} \...
Dan's user avatar
  • 15.8k
2 votes

What is the order of $p_{1}^{x} \bmod{n}$ where $p_1$ is a prime factor of $n$

Hint: $\!\bmod n\, $ suppose $p^{\Bbb N}$ has preperiod $j$ and period $k,\,$ i.e. $j,k$ are minimal such that $\,p^{j+k}\equiv p^j.\,$ Then $\,n\mid p^j(p^k-1)\,$ so $\,p^j\mid\mid n\,$ and $\,k\,$ ...
Bill Dubuque's user avatar
1 vote

Calculate the last 2 digits of the following expression

Other than the methods already presented, I will present another way by taking modulo $25$ and $4$. Note $\newcommand{\Mod}[3]{#1\equiv#2\ (\mathrm{mod}\ #3)}$ $\Mod7{-1}{4}$ so $$\Mod{7^{7^{7^7}}-7^{...
ultralegend5385's user avatar
0 votes

Calculate the last 2 digits of the following expression

We start by noticing that $7^0 = 1$ $7^1 = 7$ $7^2 = 49$ $7^3 = 343$ thus $7^3 = 43$ mod($100$) $43*7 = 301$ thus $7^4 = 1$ mod($100$) Now it's easy, since we need to check the exponents mod($4$): $...
Lucio Rosi's user avatar
2 votes
Accepted

Calculate the last 2 digits of the following expression

First: You can prove that $\forall k \in \mathbb{N} \cup \{0\}$ we have: $7^{4k+1} \equiv 7 \pmod{100}$. $7^{4k+2} \equiv 49 \pmod{100}$. $7^{4k+3} \equiv 43 \pmod{100}$. $7^{4k+4} \equiv 1 \pmod{100}...
Math Admiral's user avatar
  • 1,416
-1 votes

What is the order of $p_{1}^{x} \bmod{n}$ where $p_1$ is a prime factor of $n$

What you call the "order of $p$ modulo $pn$" will be a divisor of $\varphi(n)$. There is no "formula" that will tell you which divisor it is.
Ethan Bolker's user avatar
  • 97.7k
1 vote
Accepted

Solving $a = x \mod b$ without congruences

If you are looking for a solution of an equality $a = x\mod{b}$, instead of what we usually care about, i.e. the congruence, you have to be clear about what $x \mod{b}$ means. I also wonder what kind ...
jMdA's user avatar
  • 1,568
1 vote

reverse construction chinese remainder theorem

All you need to do is consider the $x$ you constructed modulo $p$ and $q$. From the formula that defines $Y$ and $X$ I get $1 = pX + qY \equiv qY \mod{p}.$ Plugging this into the equation for $x$ ...
jMdA's user avatar
  • 1,568
2 votes

Examining whether the relation "$aRb$ iff $a + 2b \equiv 0 \pmod 3$" is reflexive, symmetric, antisymmetric, or transitive

The symmetry proof is nonsense. You're assuming that $aRb$ and $bRa$ to be true at the outset, and reach an unclear conclusion. The definition of symmetry is: if $aRb$ is true, then $bRa$ is also true....
PrincessEev's user avatar
  • 45.8k
1 vote

Help with understanding the solution set of a lemma

Since $r$ is a solution module $m/d$, you can require $0 \leq r < m/d$. Therefore, equation (1) uses $r < m/d$ and $k \leq d-1$.
Functor's user avatar
  • 1,156
2 votes

Does there exists an integer-coefficient polynomial that extracts the highest digit of an integer in base p?

It is still not clear to me what exactly is being asked because the question mixes binary mods (=the remainder function) and quotient rings, and the range of the variable is unclear. Anyway, the point ...
Jyrki Lahtonen's user avatar
0 votes

Does there exists an integer-coefficient polynomial that extracts the highest digit of an integer in base p?

The ring $\mathbb{Z}_{p^n}$ is not a field. So it may fail to interpolate a polynomial in $\mathbb{Z}_{p^n}[X]$. This failure means that you can not find $f(X) \in \mathbb{Z}_{p^n}[X]$ to extract the ...
Functor's user avatar
  • 1,156
0 votes

Does there exists an integer-coefficient polynomial that extracts the highest digit of an integer in base p?

No. In the first case, $f(x)/x$ is bounded between $1/2$ and $1$; any polynomial with that property must be a linear polynomial, but no linear polynomial can work. In the second case, $f(x)$ is itself ...
Greg Martin's user avatar
-1 votes

Prove that $a^{2^n} \equiv 1 \pmod{2^{n+2}},$ where $a$ is an odd integer.

Let's prove that for any odd integer ( a ), ( a^{2^n} \equiv 1 \pmod{2^n} ) for all ( n \geq 3 ). First, we observe that ( a ) is odd, which means ( a = 2k + 1 ) for some integer ( k ). We will use ...
Iqra's user avatar
  • 1
1 vote
Accepted

$ a^2 + p b^2 = c \mod p^2 $ is always solvable?

Generalizing @J.W.Tanner's answer, this is trivially false for "50%" of the $c$'s: those which are not quadratic residues $\bmod p$. If $p\mid c$, this is true iff $\frac cp$ is a quadratic ...
Anne Bauval's user avatar
  • 39.6k
3 votes

$ a^2 + p b^2 = c \mod p^2 $ is always solvable?

It is not always solvable. Take $p=3$ and $c=2$. Modulo $9=p^2$, $\;a^2\in\{0,1,4,7\}$ and $3b^2\in\{0,3\}$, so $a^2+3b^2\equiv2$ has no solutions.
J. W. Tanner's user avatar
  • 61.5k
1 vote
Accepted

An exotic operation on repeating sequences of natural numbers such as $\overline{6,9} = 6,9,6,9,6,9, \dots$ Having to do with common subsums.

Im not sure if I understood correctly but you seem to wonder about taylor series with periodic derivatives. So maybe this is insightful. Let $$f(x) = \sum f_n x^n$$ $$g(x) = \sum g_n x^n$$ then $$T(x) ...
mick's user avatar
  • 16.4k
5 votes
Accepted

Is there a way to show that the Fibonacci subsequence $F_{6n+2}+2$ can't have any square number?

Render the Fibonacci Sequence $\bmod 4$: $1,1,2,3,1,0,1,1,2,...$ The sequence has period $6$ and $F_{6n+2}\equiv1\bmod4$. Therefore $F_{6n+2}+2\equiv3\bmod4$ and ... .
Oscar Lanzi's user avatar
  • 41.2k
1 vote

Why using primes as base in the Rabin-Miller test?

It seems to be popular to chose a to be a prime number, and my question is if there are rational reasons for that? Not really, it is just a unproofed belief of many, that primes are better filters. ...
PrimeTester's user avatar

Top 50 recent answers are included