1
vote
4answers
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 ...
0
votes
3answers
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 ...
3
votes
2answers
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 ...
1
vote
5answers
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 ...
-3
votes
2answers
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 ...
0
votes
1answer
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 ...
0
votes
0answers
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 ...
1
vote
1answer
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 ...
0
votes
1answer
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 ...
0
votes
2answers
45 views

Prove that for every $x \in \mathbb{Z}$ for which $x \geq 3$, if $x \equiv 3 \pmod 4$ then $3^x - 2 \equiv 0 \pmod 5$

Prove that for every $x \in \mathbb{Z} \geq 3$, if $x \equiv 3 \pmod 4$ then $3^x -2 \equiv 0 \pmod 5$. I was trying to use induction: Base case $(x = 3)$: If $3 \equiv 3 \pmod 4$ then $3^3 - 2 ...
2
votes
3answers
112 views

Modular arithmetic

How do I prove the following inequality with modular arithmetic? (No use of Fermat's last theorem is allowed.) $$3987^{12} + 4365^{12} \neq 4472^{12}$$
2
votes
2answers
80 views

Proving if $a_1\equiv b_1\pmod{n}$ and $a_2\equiv b_2\pmod{n}$ then we have $a_1+a_2\equiv b_1+b_2\pmod{n}$.

How can I prove if $a_1\equiv b_1\pmod{n}$ and $a_2\equiv b_2\pmod{n}$ then we have $a_1+a_2\equiv b_1+b_2\pmod{n}$? I have tried several ideas I've found online but don't really understand them. Is ...
3
votes
3answers
389 views

If $a \equiv b\pmod m$, then $\gcd(a, m) = \gcd(b, m)$

I was wondering if my proof makes any sense. $a \equiv b \pmod m$ $ m \mid a -b$ $ ml = a - b$ for some integer $l$ let $d = \gcd(a, m)$ let $c = \gcd(b, m)$ $$\frac{a}{d} = \frac{m}{d}l - ...
1
vote
2answers
67 views

congruence theorem prove

i am trying to prove this statement of congruence which is not really hard, but i am stumbling across the simple step. statement: $a \equiv b \mod m \land c \equiv d \mod m \Longrightarrow ac ...
3
votes
3answers
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 ...
4
votes
2answers
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 ...
0
votes
3answers
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 ...
3
votes
3answers
157 views

Prove equations in modular arithmetic

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$, ...
3
votes
1answer
296 views

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