Tagged Questions

5
votes
4answers
85 views

Prove or disprove the following statements involving greatest common divisor

Help with prove or disproving either of these statements would be really appreciated, one or the other is fine, I just need a start or a solution to one and I'm sure I could probably figure the other ...
3
votes
1answer
45 views

Proof involving division algorithm

I'm trying to prove the following. Let $\text{m}$ and $\text{n}$ be positive integers, $\text{n} \gt \text{m}$. Prove that if $\text{n}$ divided by $\text{m}$ leaves remainder $\text{r}$, then ...
5
votes
2answers
130 views

How to prove that for all $m,n\in\mathbb N$, $\ 56786730 \mid mn(m^{60}-n^{60})$?

How to prove $\forall m,n\in\mathbb N$: $$ 56786730 \mid mn(m^{60}-n^{60})?$$ Thanks in advance.
2
votes
5answers
126 views

Prove that if $6 \mid (2a + 4)$ and $9 \mid (12 + 3b)$ then $3 \mid (a + b)$

Could you help me with the problem below? Prove that if $6 \mid (2a + 4)$ and $9 \mid (12 + 3b)$ then $3 \mid (a + b)$. Thank you!
3
votes
3answers
109 views

Divisibility problem: show $(x-z)\mid xy+zw \implies (x-z)\mid xw+yz$

I'm stuck at this homework problem can someone help me out? Much appreciated! $$(x-z)\mid xy+zw \implies (x-z)\mid xw+yz$$ Thanks again!
4
votes
3answers
39 views

Problems with proof that $p|2^m-2^n$ if $p-1|m-n$

This was a homework assignment that I have already made unsuccesfully. However, no answers were given and I'm still curious. The question is as follows: "If $p$ is an odd prime number and $m > n$ ...
4
votes
1answer
90 views

Is it allowed to divide an equation by an expression which can be equal to zero?

I need a help in such a problem and will greatly appreciate any suggestions. I was taught, division of an equation by an expression which can be equal to zero can lead to missing roots. But I thought ...
1
vote
2answers
77 views

Finding the smallest positive integer $N$ such that there are $25$ integers $x$ with $2 \leq \frac{N}{x} \leq 5$

Find the smallest positive integer $N$ such that there are exactly $25$ integers $x$ satisfying $2 \leq \frac{N}{x} \leq 5$.
1
vote
1answer
52 views

Solve for $px + q \equiv 0\pmod r$

How would I solve for the following in general: $(px + q)\equiv 0 \pmod r$ For example, $ (2x + 1)=0 \pmod 7 $ $x = 3, 10, 17, 24, \ldots $ $(9y + 5)= 0 \pmod 3 $ $y$ has no ...
12
votes
2answers
212 views

Prove $6 \nmid [\left( \sqrt[3]{28} - 3 \right)^{-n}]$

Prove that: $$6 \not\left|\ \left\lfloor\frac 1 {(\sqrt[3]{28} - 3)^{n}}\right\rfloor \ (n \in Z^+)\right.$$ ($\lfloor x\rfloor$ = largest integer not exceeding $x$) I am very bad as English and ...
-2
votes
3answers
125 views

Count the the number of elements in a set, exactly divisible by 2 out of 3 numbers

I need a hint to solve the following problem, in a way that a 10yr old child can understand. On a blackboard, all whole numbers from 1 to 2006 were written. John underlined all numbers divisible by ...
0
votes
3answers
252 views

If an integer is divisible by 8 and 15, then the integer also must be divisible by which of the following?

I'm not going to list the choices here, mainly because I just want the general idea. If I generalize the question and was given $n$ different integers divide some integer $r$, how do I determine what ...
-3
votes
1answer
136 views

$S$ and $G$ are positive integers. Prove there exist integers $x$ and $y$ such that $x+y=S$ and $(x,y)=G$ if and only if $G\mid S$

So obviously because of the if and only if we must first prove that If there exist integers $x$ and $y$ such that $x+y=S$ and $(x,y)=G$ then $G\mid S$. And then if $G\mid S$, then there exist ...
1
vote
2answers
49 views

Suppose $p$, $q$ are distinct odd primes, $a\in\mathbb{Z}$, and $q|a^p-1$ but $q\nmid a-1$

From the assumptions above, I am trying to prove that $q=1+kp$ for some integer $k$ and that $k$ is even. My thoughts thus far: Since $a^p\equiv 1$ mod $q$, I know that by a corollary of Fermat's ...
0
votes
1answer
62 views

recurrence work [duplicate]

Possible Duplicate: Recurrence relation, Fibonacci numbers could someone possibly help me prove. thankyou. $(a)$ Consider the recurrence relation $a_{n+2}a_n = a^2 _{n+1} + 2$ with $a_1 = ...
3
votes
3answers
97 views

A problem about multiples.

For any positive integers $a$, $ b$, if $ab+1$ is a multiple of $16$, then $a+b$ must be a multiple of $p$. Find the largest possible value of $p$. I have no idea how to solve this. Please help. ...
1
vote
3answers
183 views

How to prove that $z\cdot\text{gcd}(a,b)=\text{gcd}(za,zb)$

I need to prove that $z \cdot \text{gcd}(a,b)=\text{gcd}(za,zb)$. I tried a lot, for example, looking at set of common divisors of the two sides, but I can't conclude anything from that. Can you ...
2
votes
1answer
121 views

Fastest Way To Compute below

Below is what I need to calculate efficiently. Find the number of natural numbers which is divisor of both $N$ and $K$. Find the number of natural numbers which is divisor of $N$ and is divisible ...
16
votes
5answers
4k views

If $a^2$ divides $b^2$, then $a$ divides $b$

Let $a$ and $b$ be positive integers. Prove that: If $a^2$ divides $b^2$, then $a$ divides $b$. Context: the lecturer wrote this up in my notes without proving it, but I can't seem to figure out ...
2
votes
2answers
113 views

How do I accurately count the integers(1-1000) that are not divisible by 3,4,5,6?

I have the general algorithm here that my teacher gave us( see full at http://i.imgur.com/pbzQb.png) ) To count we just divide, correct? like - 1000/3 = 333 ? What is the sigma notation used ...
2
votes
2answers
111 views

If $792$ divides the integer $13xy45z$, find the digits $x,y$ and $z$.

If $792$ divides the integer $13xy45z$, find the digits $x,y$ and $z$. I know that i have to use some divisibility test but i am stuck how to use it and solve the above example.
2
votes
5answers
149 views

whole numbers and division

Consider the whole number with one thousand digits that can be formed by writing the digits 2772 two hundred and fifty time in succession. Is it divisible by 9? Is it divisible by 11?
1
vote
0answers
147 views

Show that $\gcd(2^m-1, 2^n-1) = 2^ {\gcd(m,n)} -1$ [duplicate]

Possible Duplicate: Prove that $\gcd(a^n - 1, a^m - 1) = a^{\gcd(n, m)} - 1$ $\gcd(b^x - 1, b^y - 1, b^ z- 1,…) = b^{\gcd(x, y, z,…)} -1$ I'm trying to figure this out: ...
0
votes
4answers
213 views

Proof for divisibility rule for palindromic integers

I am studying for a test and came across this in my practice materials. I can prove it simply for some individual cases, but I don't know where to start to prove the full statement. Can you help me? ...
5
votes
5answers
2k views

Prove $\gcd(a+b, a-b) = 1$ or $\gcd(a+b, a-b) = 2$ if $\gcd(a,b) = 1$

I want to show that for $\gcd(a,b) = 1$ $a,b \in Z$ $\gcd(a+b, a-b) = 1$ or $\gcd(a+b, a-b) = 2$ holds. I think the first step should look something like this: $d = \gcd(a+b, a-b) = \gcd(2a, a-b)$ ...
4
votes
3answers
208 views

Prove that $b\mid a \implies (n^b-1)\mid (n^a-1)$

Given natural numbers $a,b,n$, prove $b\mid a \implies (n^b-1)\mid (n^a-1)$. I tried the simple method of beginning with $b\mid a \implies$ there exists a natural $k$ such that $bk=a$ and then ...
4
votes
6answers
364 views

Prove that $(n-m) \mid (n^r - m^r)$

In respect to a larger proof I need to prove that $(n-m) \mid (n^r - m^r) $ (where $\mid$ means divides, i.e., $a \mid b$ means that $b$ modulus $a$ = $0$). I have played around with this for a while ...
3
votes
2answers
513 views

$n^2 + 3n +5$ is not divisible by $121$

Question: Show that $n^2 + 3n + 5$ is not divisible by $121$, where $n$ is an integer.
0
votes
3answers
411 views

How to show that $\gcd(n! + 1, (n + 1)! + 1) \mid n$?

Let $n$ be a positive integer, $n!$ denotes the factorial of $n$. Let $d = \gcd(n! + 1, (n + 1)! + 1)$. Show that $d$ divides $n$. (Hint: notice that $(n+1)(n!+1) = (n+1)!+n+1$)