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

CHECK: Let $p$ be a prime number and let a $\in \mathbb{Z}$. Show that $p\mid a^p+a(p-1)!$

Let $p$ be a prime number and let $a \in\mathbb{Z}$. Show that $p\mid a^p+a(p-1)!$. $p\mid a^p+a(p-1)!$ if $p\mid a^p$ and $p\mid a(p-1)!$. $\gcd(p,(p-1)!)=1$ $\implies$ $ p \nmid (p-1)!$ so $p\mid ...
3
votes
1answer
32 views

Given $(a,4)=2, (b,4)=2$, prove $(a+b,4)=4$

So if $(a,4)=2,$ then $a=4k+2$, for some integer $k$ if $(b,4)=2$, then $b=4m+2$, for some integer $m$ Then $a+b=4(k+m)+4=4(k+m+1)$ So $a+b$ is a multiple of $4$, and thus, $(a+b,4)=4$. Are my ...
3
votes
2answers
29 views

Check: For the integers $a,b,c$ show that $\gcd(a,bc)=\gcd(a,\gcd(a,b)\cdot c)$

For the integers $a,b,c$ show that $\gcd(a,bc)=\gcd(a,\gcd(a,b)\cdot c)$ Proof: Let $u$ and $v$ be integers. Then $\gcd(a,b)=au+bv$. Then $c\cdot \gcd(a,b)=c\cdot(au+bv)=acu+bcv$ Let $x$ and $y$ be ...
0
votes
2answers
73 views

CHECK: Let a and b be relatively prime integers. Show that $\gcd(a^2+b^2,a+b)=$1 or 2 [duplicate]

Let a and b be relatively prime integers. Show that $\gcd(a^2+b^2,a+b)=$1 or 2 Proof: $s|a^2+b^2$ and $s|a+b$ implies $s|a^2+b^2$ and $s|(a+b)^2=a^2+b^2+2ab$ implies $s|a^2+b^2-(a+b)^2=2ab$ implies ...
0
votes
1answer
43 views

Verify my proof on elementary number theory

I've tried to prove this theorem, which is very simple, but is a kind of practice for me. Let $a,b$ be two positive integers. Therefore, if $a+b$ is a composite number, $frac(\frac{a}{l}) + ...
1
vote
2answers
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 ...
4
votes
2answers
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 ...
2
votes
1answer
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 ...
1
vote
2answers
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 ...
7
votes
3answers
810 views

Bad proof or not?

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. ...
2
votes
2answers
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 ...
0
votes
1answer
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 ...
3
votes
2answers
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$ ...
3
votes
1answer
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 ...
5
votes
4answers
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 ...
4
votes
1answer
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 ...
2
votes
1answer
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: ...
2
votes
1answer
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 ...
6
votes
0answers
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 ...
2
votes
0answers
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, ...
17
votes
3answers
710 views

My first induction proof (very simple number theory). Please mark/grade.

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 ...
1
vote
1answer
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}$ ...
1
vote
0answers
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 ...
0
votes
2answers
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 ...
0
votes
1answer
53 views

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}}$. ...
1
vote
3answers
90 views

Divisibility test for $4$

Claim: A number is divisible by $4$ if and only if the number formed by the last two digits is divisible by $4$. Here's where I've gotten so far. Let $x$ be an $(n+1)$-digit number. So $x= ...
3
votes
2answers
122 views

Intuition — If $k \in \mathbb{Z}$ and $n \ge 2$, then the n$^{th}$ root of k is either an integer or irrational.

Origin — Elementary Number Theory — Jones — p25 — Exercise 2.4 (1) How do you prefigure the answer? Proofwiki start after prefiguring it. (2) What's the intuition? This answer ...
2
votes
1answer
128 views

Modified Euclid's proof of infinite primes

Q. Alternate the proof for Euclid's infinite number of primes to show there are infinitely prime numbers of the form $6n-1$ where n is an integer. my attempt, suppose by contradiction there are ...
0
votes
0answers
60 views

Question on a “proof”

Let $\sigma(x)$ be the sum of divisors of the positive integer $x$. Define the abundancy index $I$ as $I(x) = \sigma(x)/x$. Suppose that we have the condition $$I(a^2)I(b^c) = 2.$$ Let $a$ and $c$ ...
2
votes
4answers
111 views

Stuck while trying to prove $2k^3 \geq (k + 1)^3$…

how can I prove the following: $2k^3 \geq (k + 1)^3$ This is the final part of the elaborate proof for $2^n > n^3 $ give $ n \geq 10$ I have used induction and end up with: $ 2^{K+1} > 2k^3 $ ...
3
votes
3answers
123 views

Is my intuition of “If $p \mid ab$ then $p \mid a$ or $p \mid b$” correct?

I'm studying number theory and I was given this Theorem to look at: If $p \mid ab$ then $p \mid a$ or $p \mid b$ I had the following intuition for the problem or a proof of sorts if you will. ...
7
votes
1answer
200 views

Proof that Fibonacci Sequence modulo m is periodic?

It's well known that the Fibonacci sequence modulo m (where m is any integer) is periodic. I have figured out a proof for this, but upon googling, I found proofs online that were far more complicated. ...
5
votes
2answers
125 views

Proof - There're infinitely many primes of the form 3k + 2 — origin of $3q_1..q_n + 2$

Origin — Elementary Number Theory — Jones — p28 — Exercise 2.6 To instigate a contradiction, postulate $q_1,q_2,\dots,q_n$ as all the primes $\neq 2 (=$ the only even prime) of the form $3k+2$. ...
3
votes
4answers
253 views

Determination of the last three digits of $2014^{2014}$

May I know if my proof is correct? Consider $x$ such that $2014^{2014} \equiv x \pmod{1000}.$ By Euler's theorem, $2014^{\ \psi(1000)} =2014^{\ \psi(2^3)\psi(5^3)}=2014^{400}\equiv 1 \pmod{1000}$. ...
2
votes
2answers
126 views

Determination of the last two digits of $777^{777}$

May I know if my proof is correct? Thank you. This is equivalent to finding $x$ such that $777^{777} \equiv x \pmod{100}.$ By Euler's theorem, $777^{\ \psi(100)} =777^{\ 40}\equiv 1 \pmod{100}$. ...
8
votes
1answer
96 views

Proof by induction that $\alpha^n + \beta^n \in \mathbb Z$

Let $\alpha, \beta \in \mathbb C$ such $\alpha + \beta \in \mathbb Z$ and $\alpha \beta = j \in \mathbb Z$. Prove that for all $n \in \mathbb N,\alpha^n + \beta^n \in \mathbb Z$ Is this proof ...
2
votes
1answer
28 views

Salvage of a given propostion

Consider the statement: For all integers $r$, $s$, and $a$, and natural numbers $m$, if $ra \equiv sa \pmod m$ then $r\equiv s \pmod m$. I have found this statement to be false by the counterexample ...
1
vote
0answers
87 views

Need a proofreading why all the units are satisfied $a^2-2b^2 =\pm1$ for $\mathbf{Z}[\sqrt{2}]$

All the units are satisfied Pell's equation $a^2-2b^2=\pm1$ for $\mathbf{Z}[\sqrt{2}]$, $a,b\in\mathbf{Z}$. Here is my proof: Let $a+b\sqrt{2}$ be a unit $\in\mathbf{Z}[\sqrt{2}]$. This implies ...
0
votes
2answers
47 views

6 is a unique number $n$ such that $n-LD(n)^2 = 2$

Let $LD(n)$ be the lowest divisor of $n$ larger than $1$. Let's find all numbers $n$ such that $n-LD(n)^2 = 2$. If $n$ is even then $LD(n) = 2$ and $LD(n)^2 = 4$. Plugging in we get $n-4=2$, so $n=6$. ...
0
votes
0answers
25 views

smallest divisor problem - proof verification

Let LD(n) be smallest divisor of n greater than 1. Let's consider the expression n-LD(n)^2. It can be proven that this expression is positive only for composite numbers. Also 6-LD(6)^2 = 2 The ...
1
vote
0answers
53 views

Could Someone Just Verify This Proof for Me? (Euler's Theorem)

I came up with this proof for my number theory class. Is it valid? Proposition: $u\in U_m \Rightarrow u^{\varphi(m)}=1$ (Where $U_m$ is the multiplicative group of integers modulo $m$) Attempted ...
1
vote
1answer
61 views

Proving (by using Zorn's lemma) that every nonempty set contains a maximal ideal

I am trying to prove the following exercise: Let $X \neq \emptyset$. Prove, (by using Zorn's Lemma) that there exists a maximal ideal in $P(X)$. Proof: Take $\mathcal{J}$ to be the set of all ideals ...