Tagged Questions
0
votes
2answers
35 views
Odditiy: An Analysis of Skew-Symmetric $n\times n$ Matrices
Let $A \in M_{n×n}(\mathbb{R})$ be a skew-symmetric matrix, i.e., $A^t = −A$. Prove that if $n$ is odd, then $\det{A} = 0$.
3
votes
1answer
34 views
$\mathbb{Z}/m\mathbb{Z}$: A Complete Set of Representatives
So, I'm letting ${\scr{A}}=\{a_1,\dots,a_n\}$ be a complete set of representatives (C.S.R.) for $\mathbb{Z}/m\mathbb{Z}$. I'm considering all $b\in \mathbb{Z}$ and seeing if ${\scr{B}}=\{a_1+b, a_2+b, ...
3
votes
1answer
121 views
Prove that there exist infinitely many squares $a$ such that $\sqrt{\sqrt{a}}$ is a square
I was just thinking about squares while randomly punched numbers into my calculator and I was wondering do there exist infinitely many squares such that $\sqrt{\sqrt{a}}$ is a square and $a$ is also a ...
3
votes
1answer
103 views
Is my proof correct? $p_1p_2p_3\cdots p_n+1)$ cannot be the square of an integer
Prove that $p_1p_2p_3\cdots p_n+1$, where $p_n$ is the $n^{th}$ prime, cannot be the square of an integer.
Let $p_1p_2p_3\cdots p_n+1=Q$ and assume it is the square of an integer, so ...
1
vote
1answer
53 views
Proof Technique and Factorials
I need to prove that $\;n!+m$ is divisible by $m$ for all integers $n \ge 2$ and $1 \le m \le n$.
2
votes
2answers
87 views
Proving $r_0+r_1a+r_2a^2+\cdots+r_{k-1}a^{k-1} < a^k$ by INDUCTION.
Let $a$ be a natural number $>1$. For all integers $r_0, r_1, \dots, r_{n-1}$ with $0\leq r_{j} < a$, then
\begin{eqnarray}
r_0+r_1a+r_2a^2+\cdots+r_{n-1}a^{n-1} < a^n.
\end{eqnarray}
...
2
votes
2answers
70 views
Prove by contradiction using division algorithm
Let $z$ be a primitive $n$-th root of unity. Prove that for any $k\in\mathbb{Z}$, if $z^k=1$, then $n \mid k$.
2
votes
5answers
165 views
Easiest and most complex proof of $\gcd (a,b) \times \operatorname{lcm} (a,b) =ab.$
I'm looking for an understandable proof of this theorem, and also a complex one involving beautiful math techniques such as analytic number theory, or something else. I hope you can help me on that. ...
0
votes
0answers
49 views
discrete logarithms
Let $g, h$ be primitive roots mod $n$. Show that $\log_h(y) = \log_h(g)\log_g(y) \pmod{ \varphi(n)}$.
I don't really know where to begin with this. I've tried rewriting the problem to get this:
...
0
votes
1answer
45 views
Primitive roots for composite modulus
If $a$ is a primitive root modulo $m_1m_2$, prove that $a$ is a primitive root modulo $m_1$ and modulo $m_2$.
This is what I have so far:
$$\text{$a$ is a primitive root mod $m_1m_2$}$$
...
5
votes
5answers
114 views
Proving $n+3 \mid 3n^3-11n+48$
I'm really stuck while I'm trying to prove this statement:
$\forall n \in \mathbb{N},\quad (n+3) \mid (3n^3-11n+48)$.
I couldn't even how to start.
1
vote
3answers
124 views
Proving That The Product Of Two Different Odd Integers Is Odd
Okay, here is how I begin my proof:
Let $q$ and $r$ be odd integers, then $q = 2k+1$ and $r = 2m+1$, where $k,m \in Z$.
$q \times r = (2k+1)(2m+1) \implies q \times r = 4mk + 2k + 2m + 1 \implies q ...
3
votes
1answer
40 views
How might one go about proving this poorly worded theorem about divisibility with the number 3?
I was messing around and found something interesting, at least to me. Although I may not know how to delicately word this, so I hope it is clear.
Claim: Each natural number $n$, whose sequence of ...
0
votes
3answers
62 views
(Dis)prove that: $\forall a,b \in \Bbb Z, \space (a \mid b^2 \land a \le b) \to a \mid b$
So I'm trying disprove this statement. Well, I'm pretty sure it's wrong because it doesn't work when $a = 0$ . I'm just not sure if all I need to do is give that counterexample, or if there is a way ...
3
votes
2answers
52 views
Totient function and Euler's Theorem
Given $\big(m, n\big) = 1$, Prove that
$$m^{\varphi(n)} + n^{\varphi(m)} \equiv 1 \pmod{mn}$$
I have tried saying
$$\text{let }(a, mn) = 1$$
$$a^{\varphi(mn)} \equiv 1 \pmod{mn}$$
...
1
vote
3answers
141 views
How do I setup a proof using contradiction.
In specific how can I setup a contradiction proof if $3n+2$ is odd then $n$ is odd?
I don't want the answer. I just want to know how to set up the proof by contradiction.
I think that I should assume ...
4
votes
1answer
67 views
Prove: $n \in \mathbb{Z} \implies 4 \nmid (n^2-3)$
I'm trying to write a contrapositive proof. What I have seems somewhat legit, but it uses proof by contradiction couched within a contrapositive proof. Since this problem is presented before the ...
2
votes
2answers
57 views
Proving solutions exist in a system of linear congruences
Suppose we have integers $a, b$, and $p$ where $p$ is prime. We also have naturals $n$ and $m$, where $n < m$.
Prove that the system of linear congruences:
$$x \equiv a \pmod{p^n}$$
...
1
vote
2answers
68 views
Prove $\forall a,b,c \in \Bbb{Z} : \gcd(a,bc) | \gcd(a,b)\cdot\gcd(a,c)$
I'm having trouble proving this statement:
$\forall a,b,c \in \Bbb{Z} : \gcd(a,bc) | \gcd(a,b)\cdot\gcd(a,c)$,
without using the fundamental theorem of arithmetic (hasn't been taught yet).
What ...
1
vote
2answers
75 views
Will some $m$ and $n$ always exist for $m(coprime_1)-n(coprime_2)=1$?
That is, is it guaranteed that, given any $2$ numbers, $p$ and $q$, such that $(p,q)=1$, there will exist $m$ and $n$ so that $mp-nq=1$?
It seems like there should be, but it would be nice to have a ...
0
votes
0answers
44 views
Question regarding a Limit involving Logs.
Suppose $A$ is a positive integer and $\delta>0$. Assume the $(n_i)$ are the denominators of a continued fraction representation of the irrational number $[0,a_1,a_2\ldots],$ where $a_{k+1}=A$ ...
0
votes
4answers
55 views
Help with a short inequality
I am not 100% sure if this statement is even true, but I think it is. Any help would be great, I have tried to prove this, but I really haven't gotten anywhere constructive with this,
If $a+b = 1$ ...
0
votes
3answers
63 views
How would one prove that $\sqrt{n}$ is the largest divisor that needs to be checked to determine if $n$ is prime?
Prove the statement:
$\forall n \in \mathbb{N}$,$\forall m \in \{2, 3,...,floor(\sqrt{n})\}$, $m$ does not divide $n \implies n$ is prime
English: If you cannot find a natural divisor > 2 ...
0
votes
3answers
213 views
Can you show why zero divided by zero does not equal zero?
I was talking about division by zero with my discrete math instructor, and it was explained to me that dividing can be broken down into simpler terms, i.e: Consider 6 divided by 3. To reach the answer ...
0
votes
5answers
298 views
How can I algebraically prove that $2^n - 1$ is not always prime?
This question is from Elementary Number Theory by W. Edwin Clark.
Is $2^n - 1$ always prime, or not? Prove.
Is this a start? $x^n - 1 = ( x - 1)(1 + x + x^2 \cdots x^{n - 1})$. So, $2^n - 1 = ...
38
votes
4answers
2k views
Prove every odd integer is the difference of two squares
I know that I should use the definition of an odd integer ($2k+1$), but that's about it.
Thanks in advance!
1
vote
2answers
60 views
Show that: $t_{n-1}+t_n=n^2$
How to can prove that :
$$ t_{n-1}+t_n=n^2.$$
where $t_n$ is number of points with integers coordinates in a square isosceles triangle of side $n$:
http://i45.tinypic.com/ndse9.jpg
2
votes
2answers
111 views
Proof : $2^{n-1}\mid n!$ if and only if $n$ is a power of $2$.
I want to prove that:
$2^{n-1}\mid n!$ if and only if $n$ is a power of $2$.
0
votes
2answers
49 views
Help with my flawed proof (A sequence of reals with 2 limits).
$(n_k)$ is a sequence of denominators for the sequence of prinicpal convergents of some irrational number, so $n_k \rightarrow \infty,\delta>0$. Let $0<\varepsilon \ll \delta$. I'm also given ...
2
votes
1answer
110 views
multiple approaches/ways to prove that $1000^N - 1$ cannot be a divisor of $1978^N - 1$
Am interested in learning to do multiple proofs for the same problem, and hence I chose this problem:
Prove that for any natural number $N$,
$1000^N - 1$ cannot be a divisor of $1978^N - 1$. ...
2
votes
5answers
120 views
Prove that $\forall n \in \mathbb{N} , 7\mid(2^n-1) \iff 3\mid n$
Prove that $\forall n \in \mathbb{N} , 7\mid(2^n-1) \iff 3\mid n$. The hint is to look at the table of $\Bbb Z/7\Bbb Z$ powers of $2 \bmod 7$, and to notice how they repeat. I'm not sure if I should ...
1
vote
1answer
62 views
Equivalence relation if $n>0$, $ n\mid (a-b)$
prove that if $n>0$ is a positive integer then relation $\equiv_n$ on integers defined by $a\equiv_n b$ if $n\mid (a − b)$ is an equivalence relation. what if $n=2$?
so i know we have to proof ...
2
votes
3answers
114 views
Proof about gcd and remainders [duplicate]
Possible Duplicate:
Why is $\gcd(a,b)=\gcd(b,r)$ when $a = qb + r$?
Prove: $\gcd(a, b) = \gcd(a+bq, b)$
Proof:
By the division algorithm we know:
$a = b\cdot q + r \iff r = a -b\cdot q$ ...
3
votes
2answers
983 views
Proof of $\gcd(a,b)=ax+by$
Here is my proof of $\gcd(a,b)=ax+by$ for $a, b, x, y \in \mathbb{Z}$. Am I doing something wrong? Are there easier proofs?
$a,b \in \mathbb{Z}, g=\gcd(a,b)$ and suppose $g \neq ax + by$. Let $c$ be ...
4
votes
5answers
982 views
What's the proof that the Euler totient function is multiplicative?
That is, why is $\varphi (A\cdot B)=\varphi (A)\cdot \varphi (B)$, if A and B are coprime? It's not just a technical trouble—I can't see why this should be, intuitively: I bellyfeel that its ...
4
votes
1answer
104 views
Divisibility of consecutive natural numbers
I found this task followed by a hint,that I should try to apply Chinese remainder theorem to that:
Prove, that there exist 2012 consecutive natural numbers,which satisfy that every one of them is ...
5
votes
1answer
148 views
Proving there are infinitely many primes of the form $a2^k+1.$
Fix $k \in \mathbb{Z}_+$. Prove that we can find infinitely many primes of the form $a2^k +1,$ where $a$ is a positive integer.
We can use the result that:
If $p \ne 2$ is a prime, and if ...
5
votes
2answers
134 views
Divisibility by sum of digits
Can anyone help me with such task?I'm preparing for my exam session and got stuck with that:
Prove, that for every natural number $n$, there exists another natural number $S$,which is divisible by ...
4
votes
4answers
894 views
Prove that there do not exist positive integers $x$ and $y$ with $x^2 - y^2 = n$
I'm working on a homework problem that is as follows:
Suppose that $n$ is a positive even integer with $n/2$ odd. Prove that there do not exist positive integers $x$ and $y$ with $x^2 - y^2 = n$.
...
2
votes
3answers
252 views
Is this statement stronger than the Collatz conjecture?
$n$,$k$, $m$, $u$ $\in$ $\Bbb N$;
Let's see the following sequence:
$x_0=n$; $x_m=3x_{m-1}+1$.
I am afraid I am a complete noob, but I cannot (dis)prove that the following implies the ...
0
votes
2answers
87 views
Prove or Disprove $xa \equiv 1 \pmod{ n}$
If $a\in\mathbb{Z}, n\in\mathbb{N}$, then the equation $xa\equiv1\pmod {n}$ has a solution for some $x\in\mathbb{Z}$.
I'm not quite sure where to start. I know that $n|(xa-1)$, so $ns=xa-1$ for some ...
3
votes
6answers
189 views
Prove if $x^{2}-5xy-3$ is even, then $x+y$ is odd, where $x,y \in\mathbb{Z}$
I know for you this is easy but for me is not. I give my best shot but it's no use so I need someone to teach about all this stuff.
As I try to solve this one, I come up with this answer:
Suppose ...
3
votes
4answers
174 views
Prove that there exists a natural number n for which $11\mid (2^{n} - 1)$
I'm thinking putting it into modulo form: there exists a natural number $n$ for which
$$2^{n}\equiv 1 \pmod {11}$$
but I don't know what to do next and I'm still confused how to figure out ...
0
votes
3answers
159 views
How to prove $p$ divides $a^{p - 2} + a^{p - 3} b + a^{p - 4} b^2 + \cdots + b^{p - 2}$ when $p$ is prime, $a, b \in \mathbb{Z}$ and $a,b \lt p$?
If $p$ is a prime number and $a, b \in \mathbb{Z}$ such that $a,b \lt p$, then how could we prove that $p$ divides
$\left(a^{p - 2} + a^{p - 3} b + a^{p - 4} b^2 + \cdots + b^{p - 2}\right)$?
16
votes
5answers
990 views
Prove that every number ending in a $3$ has a multiple which consists only of ones.
Prove that every number ending in a $3$ has a multiple which consists only of ones.
Eg. $3$ has $111$, $13$ has $111111$.
Also, is their any direct way (without repetitive multiplication and ...
0
votes
2answers
138 views
Proving $2^{\varphi(n)}\ge n$
To show $n\in\mathbb{N}\setminus \{6\}\Rightarrow 2^{\varphi(n)}\ge n$
I can't follow the proof from
http://mathematicalspectacles.blogspot.de/2012/05/interesting-study-of-zsigmondy-primes.html
...
3
votes
0answers
52 views
Lucasian Criterion for the Primality of $3\cdot 2^n+1$
Note : This problem has no specific source
Def :
Let's define number $N$ as : $N=3\cdot 2^n+1$
Def :
Let's define starting seed $S$ as :
$S =
\begin{cases}
32672, & \text{if } n\equiv 1 ...
2
votes
3answers
101 views
Positive integers expressed in the form : $\frac{a^b+c}{a+c}$
Note : This problem has no specific source .
Is it true that :
Every positive integer $n$ greater than $1$ can be expressed in the form :
$n=\frac{a^b+c}{a+c}$ , where $a,b>1$ , and $c ...
2
votes
3answers
190 views
If $n=p^{a_1}_1\cdot p^{a_2}_2 \ldots p^{a_k}_k $ and $p^{n-1}_i \equiv r_i \pmod n$ then $r_i>1$?
Note : This problem has no specific source .
Let $n$ be a composite number of the form :
$n=p^{a_1}_1\cdot p^{a_2}_2 \ldots p^{a_k}_k $ , where $p_1,p_2 , \ldots p_k$ are distinct primes and ...
1
vote
1answer
70 views
Greatest $n$ that can be written in the form of $ax+by=n$
In a diophantine equation $ax + by = n$ with $(a, b) = 1$, the greatest possible value of $n$ such that both $(x, y)$ are not positive is $ab − b − a$?
This is given in my module (without any proof). ...
