1
vote
3answers
65 views

Prove that $17$ divides $9a + 5b$

So, according to the book, for all $a, b, c$ that are elements of integers, it holds that $a|b$ implies $a|bx$ for all $x$ that is an element of integers. In other words it works for all ARBITRARY $x$ ...
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 ...
3
votes
5answers
576 views

The sum of three consecutive cubes numbers produces 9 multiple

I want to prove that $n^3 + (n+1)^3 + (n+2)^3$ is always a $9$ multiple I used induction by the way. I reach this equation: $(n+1)^3 + (n+2)^3 + (n+3)^3$ But is a lot of time to calculate each ...
1
vote
2answers
35 views

Contrapositive proof using rule of divisibility

Suppose $x,y,z$ are integers and $x \neq 0 $ if $x$ does not divide $yz$ then $x$ does not divide $y$ and $x$ does not divide $z$. So far I have: Suppose it is false that $x$ does not divide $y$ and ...
0
votes
1answer
24 views

Prove superpolynomial growth rate [duplicate]

Let $p(n)$ be the number of partitions of $n$. Prove that growth rate of $p(n)$ is superpolynomial, meaning that for every given $k$ there is $p(n)= \omega (n^k)$.
1
vote
4answers
57 views

Help with groups

let $G$ be a finite group with $e$ Identity element and let $a$ and $b$ belong to $g$ prove that if: $\gcd(o(a),o(b)) =1$ then $\langle a \rangle \cap \langle b \rangle = \{ e \}$. if someone can ...
2
votes
1answer
44 views

Prove $\gcd(k, l) = d \Rightarrow \gcd(2^k - 1, 2^l - 1) = 2^d - 1$ [duplicate]

This is a problem for a graduate level discrete math class that I'm hoping to take next year (as a senior undergrad). The problem is as stated in the title: Given that $\gcd(k, l) = d$, prove that ...
1
vote
0answers
14 views

Efficient way needed

Given N, M find the : GCD(1, 1) * GCD(1, 2) * … * GCD(1, M) * GCD(2, 1) * GCD(2, 2) * … * GCD(2, M) * … * GCD(N, 1) * GCD(N, 2) * … * GCD(N, M) modulo 10^9+7 Constraints: 1 <= N, M <= 2 * ...
2
votes
0answers
55 views

Prove the following : [duplicate]

Prove the following : $$ {{n}\choose{7}}-\left \lfloor{\frac{n}{7}}\right \rfloor $$ is divisible by 7.
1
vote
3answers
71 views

Use mathematical induction to prove that $(3^n+7^n)-2$ is divisible by 8 for all non-negative integers.

Base step: $3^0 + 7^0 - 2 = 0$ and $8|0$ Suppose that $8|f(n)$, let's say $f(n)= (3^n+7^n)-2= 8k$ Then $f(n+1) = (3^{n+1}+7^{n+1})-2$ $(3*3^{n}+7*7^{n})-2$ This is the part I get stuck. Any help ...
2
votes
1answer
85 views

Prove $\gcd(ka,kb) = k*\gcd(a,b)$

For all $k > 0,\ k\in \Bbb Z$ . Prove $$\gcd(k*a,\ k*b) = k *\gcd(a,\ b)$$ I think I understand what this wants but I can't figure out how to set up a formal proof. These are the guidelines we ...
0
votes
1answer
33 views

proof with divisibility

this is the original question prove: $\forall c \in Z, a\neq 0 $and b both $ \in Z$ $a|b \iff c\cdot a|c\cdot b$ Then he corrected himself by saying for problem 1: to show that ca | cb implies a | b ...
6
votes
3answers
81 views

Show that $9\mid a^2$ if given that $6\mid a$

Does this prove I made seem correct to show that if $6$ divides $a$ then $9$ divides $a^2$ If $6\mid a$, then $a = 6k$ (k is some integer). Then $a^2 = 36k^2 = 9(4k^2)$. Which means that $9\mid ...
4
votes
1answer
236 views

The product of any three consecutive natural numbers is divisible by 9.prove or find a counterexample

can anyone give me feedback on my solution false counterexample: n(n+1)(n+2) let n= 1 1(2)(3) =6 is not divisible by 9 is this correct?
1
vote
1answer
43 views

Show that $gcd(a,b) |d $ and hence $gcd(a, b) \leq d$, where $d$ is the smallest number of the form $ma+nb$

Show that if $d$ is the smallest element in the set $S = \{s \in \mathbb{N} | \exists m,n \in \mathbb{Z}, s = ma+ nb \}$ such that $d = ax + by$ then $\gcd(a,b) |d $ and hence $\gcd(a, b) \leq d$
0
votes
2answers
18 views

Show that for any $s \in S$ where $S = $ {$s \in \mathbb{N} | \exists m,n \in \mathbb{Z}$, we have $d|s$ where $d$ is the smallest element

Explain why the set $S = $ {$s \in \mathbb{N} | \exists m,n \in \mathbb{Z}, s = ma+ nb $} has a smallest element, call it d, so we know there exists $x,y \in \mathbb{Z}$ such that $d = ax + by$, and ...
0
votes
0answers
31 views

Prove that $s \not= \emptyset $ by showing that at least one of $|a|$ or $|b|$ is an element of $S$.

. I'm trying to show an alternative proof to Bezout's Lemma (let $a, b \in \mathbb{Z}$, then there exists $x,y \in \mathbb{Z}$ such that $gcd(a, b) = ax + by$). Heres one of the steps in proving it: ...
0
votes
0answers
25 views

Is this division proof correct?

Show that if a is an even integer then 2 divides a. Let a be 2k 2/2k By Division Algorithm 2k=2q so k=q I'm not sure if this is the correct way to go about it so any insight helps. Thanks!
1
vote
2answers
33 views

Show the equivalence: $ab|c \iff a|c$ and $b|c$

Let $a,b \in \mathbb{Z}$ \ {$0$} with $gcd(a, b) = 1$ and let $c \in \mathbb{Z}$. Show the equivalence: $ab|c \iff a|c$ and $b|c$ Also give an example of numbers $a,b \in \mathbb{Z}$ \ {$0$} and ...
0
votes
2answers
35 views

How would I prove for all a that a divides zero

I'm trying to prove for all a such that a divides zero. I can explain verbally why it works but I can't seem to be able to write it down in "proof" form. Could someone help me out?
3
votes
3answers
513 views

What are all positive divisors of 7 factorial?

I need to determine all the positive divisors of 7!. I got 360 as the total number of positive divisors for 7!. Can someone confirm, or give the real answer?
0
votes
4answers
99 views

Show {$ ax + by | x, y \in \mathbb{Z}$} = {$n$ gcd$(a,b)|n\in \mathbb{Z}$}

I have the following problem: Let $a, b \in\mathbb{Z}$. Show that {$ ax + by | x, y \in \mathbb{Z}$} = {$n$ gcd$(a,b)|n\in \mathbb{Z}$} I understand that the Bezout's lemma says that $gcd(a,b) = ...
1
vote
1answer
40 views

show that for any $n \in \mathbb{Z}$ gcd($n^2 - n + 1, n +1)$ is either $1$ or $3$.

show that for any $n \in \mathbb{Z}$ gcd($n^2 - n + 1, n +1)$ is either $1$ or $3$. My Work: I considered the case where $n =-1$ , and the case $n \not= 1$. So when $n\not= -1$ we can let $n^2 - ...
0
votes
0answers
75 views

How do you justify the PigeonHole principle?

I am working on the problem below and just have two questions pertaining to my answers. 1) Am I clearly and correctly justfying my answers, anything I can improve on or explain better? 2) Are my ...
0
votes
1answer
67 views

Understanding a proof that $\gcd(a, b) = 1$ if $sa + tb = 21$ and $ua + vb = 10$

I am studying the solution to a problem: Suppose $a, b, s, t, u, v$ are integers such that $sa + tb = 21$ and $ua + vb = 10$. Show that $\gcd(a; b) = 1$. ...
3
votes
3answers
109 views

how to prove if $m^{2}|n^{2}$ then m|n just hint please. [duplicate]

How to prove the following?: Let $m,n\in \mathbb{N}$ ; $ \;m^{2}\mid n^{2}\Longrightarrow \;\;m\mid n$ Just a hint please. I tried two ways but did not work.
0
votes
1answer
70 views

An easy question with integer numbers

I have an easy question of arithmetic. Let $a, b, N$ be integer numbers such that $\mathrm{gcd}(a,b,N) = 1$. Is it true that there exists an integer number $x \in \mathbb{Z}$ such that ...
0
votes
4answers
135 views

Discrete math: proving gcd's and other fomulas

I have two questions: Suppose $a,b,s,t,u,v ∈ \mathbb{Z}$ such that $sa + tb = 21$ and $ua + vb = 10$. Show that $gcd(a,b) = 1.$ I feel like I'm going about this one in the wrong way. We haven't ...
0
votes
2answers
154 views

Find a pair of integers x and y such that 17369x + 5472y = 4

I'm doing discrete math. Been stuck on this problem forever. I need to find a pair of integers x and y such that 17,369x + 5472y = 4 I understand that I need to use the division algorithm. But what ...
0
votes
2answers
44 views

Euclidean lemma proof [duplicate]

According to Euclidean lemma it is defined that if $p$ is prime then $$p|ab\Rightarrow p|a\lor p|b$$ How to prove by descending induction that if $$p|a^n \Rightarrow p|a $$ knowing that $a^n = a ...
0
votes
1answer
73 views

Divisibility of prime numbers

I have this exercise in my worksheet in the discrete mathematics course.I don't understand the part that deals with prime numbers in integer-divisibility. "Show that for a prime number $p$, if a ...
1
vote
1answer
292 views

Finding equivalence classes

Consider the equivalence relation on Z x Z given by (m,n)R(p,q) if and only if mq = np 1) Find the equivalence class represented by (2; 5) 2) Describe the set S of the equivalence classes ...
0
votes
3answers
78 views

If $a|(b-c)$ does it follow that $a|(b+c)$?

I plug in numbers and this seems to work but how can this be proved? If: $a|(b-c)\space \rightarrow\space ak=b-c$, but I can't see how this would mean $a|(b+c)$ If this is true, how can this be ...
0
votes
2answers
35 views

Prove $(\forall n \in \Bbb N)[\gcd\left(n,(16n+1)^3\right)=1]$

Prove $(\forall n \in \Bbb N)[\gcd(n,(16n+1)^3)=1]$ Knowing that $\gcd(a,b)=\gcd(a,b+a\times k)$ with $k \in \Bbb Z$ $$\gcd\left(n,(16n+1)^3\right)=\gcd\left((16n+1)^3,n\right)=d$$ ...
0
votes
1answer
46 views

Inductive proof for gcd

Proof that $(\forall n \in \Bbb N)[\gcd(n,(25n+1)^3)=1]$ By the inductive method: $p(n):\gcd(n,(25n+1)^3)=1$ $p(1): \gcd(1,26^3)=1 \implies p(n)\equiv \text{True}$ $p(n): $I assume that $p(n)\equiv ...
1
vote
6answers
261 views

Prove that if $m^2 + n^2$ is divisible by $4$, then both $m$ and $n$ are even numbers.

Let $m$ and $n$ be two integers. Prove that if $m^2 + n^2$ is divisible by $4$, then both $m$ and $n$ are even numbers. I think I have to use the contrapositive to solve this. So I assume $\neg ...
-1
votes
2answers
53 views

For any integer $n\ge0$ it follows that $9\mathrel|(4^{3n}+8)$?

I have been trying to use induction in order to prove the above statement but I always reach a dead end. How can this statement proven via induction? Thank you!
0
votes
5answers
104 views

Proof: $\;n^2\;$ is even if and only if $\;n\;$ is even.

Please help how would you go about doing this? I'm studying for a final. This is on a study guide. I'm having a lot of trouble with this class. Prove that $n^2$ is even if and only if $n$ is even. ...
1
vote
2answers
2k views

How many positive integers less than 1000 are divisible [closed]

How many positive integers less than 1000 c) are divisible by both 7 and 11? d) are divisible by either 7 or 11? e) are divisible by exactly one of 7 and 11?
1
vote
3answers
55 views

If $d$ is a common divisor of $m$ and $n$, then so it is of $n$ and $m-n$

I am having trouble proving the following statement: Prove that for all integers $m$ and $n$, if $d$ is a common divisor of $m$ and $n$ (but $d$ is not necessarily the GCD) then $d$ is a common ...
2
votes
3answers
86 views

Prove that if $a|b$ and $a|c$, then $a\mid(c-b)$.

I'm having trouble proving this one. I know its true. Any ideas? Here is what I have so far: If $a\mid b$, then there exists an integer $q_1$ such that $b = aq_1$. If $a\mid c$, then there exists an ...
18
votes
4answers
1k views

Is the number $333, 333, 333, 333, 333, 333, 333, 333, 334$ a perfect square?

I know that if the number is a perfect square then it will be congruent to 0 or 1 (mod 4). Now since the number is even, I know that it is either 0 or 2 (mod 4). How would I go about answering this? ...
3
votes
4answers
60 views

Is $\mbox{lcm}(a,b,c)=\mbox{lcm}(\mbox{lcm}(a,b),c)$?

$\newcommand{\lcm}{\operatorname{lcm}}$Is $\lcm(a,b,c)=\lcm(\lcm(a,b),c)$? I managed to show thus far, that $a,b,c\mid\lcm(\lcm(a,b),c)$, yet I'm unable to prove, that $\lcm(\lcm(a,b),c)$ is the ...
0
votes
2answers
401 views

For all integers a, b, c, if a | b and b | c then a | c. [duplicate]

Is this T or F? and most importantly, why? I'll be using any answers for a basis or completely my other questions, since my understanding is still a little poor.
0
votes
1answer
166 views

Divisibility Discrete Math

For all integers a, b, c, if a | (b + c), then a | b and a | c True or false? Im assuming it's false because if you make a=2 b=3 and c=4, it won't work
0
votes
1answer
68 views

Divisibility of a number by $(4k+3)$ in minimum time

Please suggest any algorithm with minimum time complexity to check whether a number $n$ is divisible by at least one $(4k+3)$ where $k>0$ is integer and $(4k+3)\le n$?
3
votes
3answers
686 views

Use mathematical induction to prove that 9 divides $n^3 + (n + 1)^3 + (n + 2)^3$; Looking for explanation, I already have the solution.

I have the solution for this but I get lost at the end, here's what I have so far. basis $n = 0$; $9 \mid 0^3 + (0 + 1)^3 + (0 + 2)^2 ?$ $9 \mid 1 + 8$ = true Induction: Assume $n^3 + (n + ...
2
votes
1answer
68 views

A problem relying on van der Waerden's theorem, and the existence of sums divisible by a given number $n$

Say we are given a sequence of integers $\{a_i\}_{i \in \mathbb{N}}$, as well as a pair of integers $n, m$. How can we show that there always exist positive integers $s, r$ such that the sums $a_s + ...
0
votes
4answers
72 views

Divisibility for natural numbers

Prove that $(\forall n \in \Bbb N)(4 \mid 5^n-1 )$ I only know that if $ a \mid b \implies b =a \times q $ with $a,b,q \in \Bbb Z$ So(...) $4\mid5^n-1 \implies 5^n-1 = 4 \times q$ But I can't ...
17
votes
4answers
369 views

Prove that $\dfrac{(n^2)!}{(n!)^n}$ is an integer for every $n \in \mathbb{N}$

Prove that $\dfrac{(n^2)!}{(n!)^n}$ is an integer for every $n \in \mathbb{N}$ I know that there are tools in Number theory to proves the required but I want to use the tool that says that if you ...