# Tagged Questions

46 views

### Discrete Mathmatics Proof

Here is the question: $a$ and $b$ are any two integers. $c$ is any prime. Prove that if $c$ divides $ab$, then $c$ divides $a$ or $c$ divides $b$ (or both, as in it can divide either or both, i.e. ...
38 views

### If $x$ is an integer and $x \ge 5$, then there's $y$ such that $x + y$ is a perfect square with $x > y$.

$y < 5 \le x$ by hypothesis. Let $y = -x$. Then, $-x + x = 0$. Since $0$ is a perfect square, we are done. I am not sure if this proof would fly. Please, tell me what you think.
19 views

### Number solutions of congruence

Let $f(x)=a_nx^n+a_{n-1}x^{n-1}+\dots+a_1x+a_0$ and $f(x)\equiv 0 \pmod p$ have more than $n$ solutions. Then $p\mid a_i$ for $i=0,1,\dots,n$. My proof: Let $m$ be the maximal such that $p\nmid a_m$ ...
58 views

### Prove $(a,b,c)=((a,b),(a,c))$

The notation is for the greatest common divisor. I know that $$(a,b,c)=((a,b),c)=((a,c),b)=(a,(b,c))$$ Suppose $g=(a,b,c)$. Then $g\mid a,b,c$. Also, $g\mid(a,b),c$ and $g\mid(a,c),b$. Thus ...
42 views

### Generalized Induction Verification

Consider the following simple exercise. Prove or disprove: $\gcd(km, kn) = k \gcd(m, n)$, where $m, n, k$ are natural numbers. Now, this is easy to prove using prime factorization. Knowing that ...
49 views

### Proof for modulus via direct or contrapositive

I have to prove the following via direct proof or via contra positive. For $a,b\in \mathbb{Z}$ it follows that $(a+b)^3 \equiv a^3 + b^3 \mod 3$ I'm unsure of the best way to approach this ...
19 views

### Determining the number of solutions of the equation $y^2 = x^3 + x^2 + 5$ in $\mathbb{Z}/p^k \mathbb{Z}$ in function of $k$.

I found a question that asked me to discuss the number of solutions of the equation $y^2 = x^3 + x^2 + 5$ in $\mathbb{Z}/p^k \mathbb{Z}$ in function of $k$. I would like to use the multivariate ...
64 views

### Proof that there are infinitely many primes of the form $6k+1$. Proof verification

Theorem. there are infinitely many primes of the form $6k+1$. I've just proved that there are infinitely many primes of the form $6k+1$. Could you please check my proof? At first, I proved that ...
42 views

60 views

### Ground Plan - Prove Fermat-Euclid's Totient Theorem with Lagrange's Theorem

If $\gcd(a,n) = 1$, then $a^{\phi(n)}\equiv 1\pmod n$. Here's a three-step proof. An integer a is invertible means there's some $a^{-1}$ such that $aa^{-1}\equiv 1 \pmod n$. By cause of Jones p84 ...
167 views

### Fermat's Little Theorem fails for composite instead of prime numbers.

I know Fermat's Little Theorem = Fermat-Euler's Totient Theorem when $n$ is prime. Elementary Number Theory, Jones, p83 writes if we simply replace p with a composite integer n, then the ...
64 views

### Backward direction – Wilson’s Theorem – p is prime $\iff (p-1)!\equiv-1(mod\ p)$.

(1) How can you preconceive to prove by contradiction? Prove by contradiction. Suppose $n$ is composite. This means there exists a divisor $d|n$ such that $1<d<n$. We are given that ...
39 views

### Ground Plan – Forward direction – Wilson’s Theorem – p is prime $\iff (p-1)!\equiv-1(mod\ p)$.

Lemma 5.3 - I omit proof here - Let p be prime. Then $x^2 \equiv 1 \, (mod p) \iff x \equiv \pm 1 \; (mod p)$ First we establish the result for the first two primes 2, 3. Then prove the result for ...
810 views

Can you prove this: Let $a,b \in \mathbb{N}$. If $a + b + ab = 2020$ then $a+b=88$. This is the attempt given: $\frac{2020-88}{a b}=1$ $a+b=88$ Substituting for b using the 2nd equation. ...
109 views

### Solve $ax \equiv b \mod m$ without Linear Congruence Theorem or Euclid's Algorithm?

Origin page 5. The overhead doesn't look like Linear Congruence Theorem or anything from Euclid's Algorithm. page 4 tries to delineate ...
36 views

### Error in this Chinese Remainder Theorem problem with three congruence equations?

Origin - p5 - Example 5 I'm querying a possible error, thence I show the pdf as is. Is the 3 underlined in red supposed to be 2? scilicet, the last line should be $n = 2 \times 5 \times 7$? Notation ...
94 views

### Is this proof rigorus?

Simple abstract algebra proof: Suppose that $a,b,c\in\mathbb{Z}$ with $a$ and $b$ relatively prime. If $a|bc$, then $a|c$. Proof 1 Since $a$ & $b$ relatively prime, $a|bc\Rightarrow a|c$ ...
50 views

### Show: $\varphi\colon\mathbb{Z}_{mn}\to\mathbb{Z}_m\times\mathbb{Z}_n, k\mapsto (k\% m,k\% n)$ is a ring isomorphism for $m$ and $n$ relatively prim

Let $m\in\mathbb{Z}, n\in\mathbb{N}$. Then there exist unique elements $q\in\mathbb{Z}, r\in\mathbb{N}$ with $0\leq r<n$ and $m=qn+r$. We write $r:=m\% n$. Let $m,n\in\mathbb{N}$ be relatively ...
397 views

### Is the reasoning/algebra for my proof correct? (musical tuning theory proof)

This isn't for a class, I was just wondering if I would be able to work out a proof for something like this myself for fun, and wanted to verify that my methods are correct. Basically, what I'm trying ...
65 views

### Proof verification: Let $a$ be an irrational number and $r$ be a nonzero rational number. If $s$ is a rational number then $ar$ + $s$ is irrational

I have to prove the following: Prove: Let $a$ be an irrational number and $r$ be a nonzero rational number. If $s$ is a rational number then $ar$ + $s$ is irrational So, I decided to do a proof ...
76 views

### Proof - Fundamental Theorem of Arithmetic using Euclid's Lemma

Let $n \in Z > 1$. Then the expression for $n$ as the product of $\ge 1$ primes is unique, up to the order in which they appear. From Proofwiki. Suppose $n$ has two prime factorizations: ...
50 views

### Linear Congruence Theorem - Are these solutions too? Where'd they hail from?

(1) Can't the signs - I colored them in red - of x and y be switched? Aren't $x = x_0 - bn/d$ and $y = y_0 + an/d$ also solutions? They satisfy $ax + by = c$? (2) How can I remember these ...
67 views

### My first proof that uses the well-ordering principle (very simple number theory). Please mark/grade.

What do you think about my first proof that uses the well-ordering principle? Please mark/grade. Theorem The sum of the cubes of three consecutive natural numbers is a multiple of 9. Proof ...
48 views

### My first proof employing strong induction / complete induction (very simple number theory). Please mark/grade.

What do you think about my first proof employing strong induction? What mark/grade would you give me? Theorem Every natural number greater than 1 is a product of one or more primes. Proof First, ...
710 views

What do you think about my first induction proof? Please mark/grade. Theorem The sum of the cubes of three consecutive natural numbers is a multiple of 9. Proof First, introducing a predicate ...
27 views

### Is this divisibility proof by induction correct/sufficient?

To show: 13 | $4^{2n+1}+3^{n+2}$ I used induction beginning successfully with n=0 (or n=1), then making the step to n+1: An x exists so that $13x = 4^{2n+3}+3^{n+3}$ $13x = 16*4^{2n+1}+3*3^{n+2}$ ...
79 views

### A question on odd perfect numbers

Let $\sigma(x)$ be the sum of the divisors of the positive integer $x$. If $\sigma(M) = 2M$, then $M$ is said to be perfect. Currently, there are $48$ known examples of even perfect numbers -- on ...
49 views

### How do $x^{p}+y^{p}=z^{p}$ and $x\equiv y \pmod{p}$ together imply $x\equiv -z \pmod{p}$?

I am reading Marcus' Number Fields and I have been a little stuck following his argument in page $4$ (where he is sketching an argument for Case 1 of Fermat's Last Theorem for primes $p$ for which ...
### How to show that if $p \equiv 1,3 \pmod 8$ then there exists a $u,v \in \mathbb Z: u^2 + 2v^2 = p$
I'm trying to show this statement: $$p \equiv 1,3 \pmod 8, \; \; \exists \; u,v \in \mathbb Z : u^2 + 2 v^2 = p.$$ I believed I proved it the other direction using the ring $\mathbb Z{\sqrt{-2}}$. ...