# Tagged Questions

29 views

### Evaluating the greatest common divisor.

I have a homework question which i'm struggling with, i would be interested in what method i should use to solve the following problems: ...
147 views

### Diophantine equation $ax + by = c$ has an integer solution $x_0, y_0$ if and only if $\gcd(a,b)|c$

Let $a,b,c$ be positive integers. Verify that Diophantine equation $ax + by = c$ has integer solution $x_0, y_0$ if and only if $GCD(a,b)|c$. Attempt Diophantine $ax + by = c$ has integer solution ...
71 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$ ...
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 ...
591 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 ...
36 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 ...
25 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)$.
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 ...
50 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 ...
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 * ...
55 views

### Prove the following : [duplicate]

Prove the following : $${{n}\choose{7}}-\left \lfloor{\frac{n}{7}}\right \rfloor$$ is divisible by 7.
77 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 ...
93 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 ...
34 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 ...
82 views

40 views

74 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 ...
303 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 ...
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 ...
37 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$$ ...
48 views

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!
106 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. ...
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?
56 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 ...
87 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 ...
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? ...
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 ...
421 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.
174 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
### 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$?