7
votes
2answers
226 views

Proving a palindromic integer with an even number of digits is divisible by 11

I'm in an introductory course for discrete math so I'm a novice at English proofs. I'm not sure if my reasoning here is valid or if I'm using modular arithmetic correctly. Specifically the line I ...
1
vote
2answers
59 views

Can this be solve using modular arithmetic? $k$ is prime $\Rightarrow$ $8k+1$ is prime

Is the following statement true or false? $\forall k \in \mathbb{N}, k$ is prime $\Rightarrow$ $8k+1$ is prime The answer is that the statement is false because if $k=7$, then $k$ is prime but ...
3
votes
5answers
90 views

How to select the right modulus to prove that there do not exist integers $a$ and $b$ such that $a^2+b^2=1234567$?

I understand the solution but I don't know how the author decided to start with modulo 4 instead of something else? What is it about the expression $a^2+b2=1234567$ that would trigger us to select ...
0
votes
2answers
28 views

Help me understand the proof of $a \equiv b \mod m \Rightarrow r_m(a)=r_m(b)$

Let: $r_m:\mathbb{Z}\rightarrow R_m$ where $r_m(a)=r\Leftrightarrow a \equiv r \mod m $ and $r\in R_m$ where $R_m$ is the set of residues modulo $m$. I understand the above proof until $r' ...
1
vote
4answers
71 views

Can anyone explain how to show that $n^{5} -n ≡0$ mod $30$ for every $ n \in \mathbb{N} $

I first tried to answer this using proof by induction, however my problem got more complicated when I got to the induction step. Is there another way of solving this problem?
1
vote
3answers
55 views

Simplifying a proof by contradiction: if $a\equiv 1\bmod 5$, then $a^2\equiv 1\bmod5$

Prove the following either by Direct Proof or by Contraposition: Suppose $a\in\mathbb{Z}$, if $a\equiv 1\pmod 5$, then $a^2\equiv 1\pmod5$ Suppose $a\equiv 1\pmod 5$ Then $5|\left(a-1\right)$, ...
1
vote
4answers
53 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
37 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
24 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
111 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
39 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
36 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
23 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
117 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
124 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
83 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
426 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
704 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
69 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
162 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
299 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: ...