# Tagged Questions

50 views

### Direct proof using modular arithmetic

Give a direct proof of $8\mid (3^n + 5^n)$ for all odd natural numbers. I know how to prove this by induction, I am not sure how to go about it using a direct proof. I would start by saying that ...
34 views

### Proof for a non-conditional statement

I'm having a bit of trouble doing this proof. If $a\in\mathbb{Z}$, then $a^3 \equiv a \pmod 3$. I know how to do proofs if there were conditional statements but not sure how to prove this with ...
18 views

### How do I eliminate mod from an expression?

If I have an expression such as $$x = ((a \bmod b) - s) \bmod t, \quad 0 < a < b$$ And I want to step to $$x = (a - s) \bmod t$$ Is acceptable to jump straight from the first expression to ...
98 views

### If $a, b$ are relatively prime proof.

Prove that if $a$ and $b$ are relatively prime integers and $ab$ is a perfect square so are $a$ and $b$. Show by counterexample that the relatively prime condition is necessary. I dont know how ...
35 views

### Proofs for modular arithmetic

$\rm(a)$ Prove that for any pair $a,b$ of positive integers there are integers $x,y\in\Bbb Z$ such that $ax+by=\gcd(a,b).\$ (Hint: Use the well-ordering principle on the set of integer linear ...
30 views

### GCD of polynomials

In $\mathbb{Z}/5\mathbb{Z}[x]$ use the Euclidean Algorithm to find the GCD of $x^4+x^2$ and $x^4+x^3+3x$. My thoughts: I am getting to the point where I need to use a fraction to get further in ...
18 views

### Question regarding a surjective function

The function $f :\mathbb{Z}_{12} \longrightarrow \mathbb{Z}_4$ is defined by $f(x)=3x$. I am asked given any $a,b \in \mathbb{Z}_{12}$ if preservation of addition and multiplication occur. I proved ...
22 views

### Finding the remainder of a linear congruence

Okay so say I have $314^{420} \equiv r \pmod{1001}$ and I have to find what the remainder is, $r$ in this case. I know you could compute it by $gcd(314^{420}, 1001)$ and using EEA. But the numbers are ...
96 views

### Modular Arithmetic - Pirate Problem

I was reading an example from my book, and I need further clarification because I don't understand some things. I'm just going to include the $f_1$ part in full detail because $f_2$ and $f_3$ are ...
45 views

148 views

### If $n\equiv 2\pmod 3$, then $7\mid 2^n+3$.

In this (btw, nice) answer to Twin primes of form $2^n+3$ and $2^n+5$, it was said that: If $n\equiv 2\pmod 3$, then $7\mid 2^n+3$? I'm not familiar with these kind of calculations, so I'd like ...
655 views

### Prove that $x^{2} \equiv -1$ (mod $p$) has no solutions if prime $p \equiv 3\pmod 4$.

Assume: $p$ is a prime that satisfies $p \equiv 3 \pmod 4$ Show: $x^{2} \equiv -1 \pmod p$ has no solutions $\forall x \in \mathbb{Z}$. I know this problem has something to do with Fermat's Little ...
67 views

### Prove how many distinct elements in the set $\{ax \pmod{m}:a\in\{0,…,m-1\}\}$

There are $\dfrac{m}{\gcd(m,x)}$ distinct elements in the set $\{ax \pmod{m}:a\in\{0,...,m-1\}\}$ I have only known these by using a computer to generate the number of distinct elements. But I am not ...
Prove or disprove the following statement in modular arithmetic. If $a\equiv b \mod m$, then $a^2\equiv b^2 \mod m$ If $a\equiv b \mod m$, then $a^2\equiv b^2 \mod m^2$ If $a^2\equiv b^2\mod m^2$, ...
### Is this a good proof of Wilson's theorem? — ($(n-1)!+1 \equiv_n 0$ iff n is prime)
Theorem: $(n - 1)! + 1 \equiv_n 0$ if and only if $n$ is prime. To prove that if $n$ is not prime this is not true is trivial, so I'm just interested in proving that this is true for all p: ...