3
votes
2answers
37 views

A sum of difference of floors

I have the sum ( $M$ is any integer $> 1$ ): $$ \sum_{h = 1}^{M}\left(\,\left\lfloor\, 2M + 1 \over h\,\right\rfloor -\left\lfloor\, 2M \over h\,\right\rfloor\,\right) $$ and looking for a way to ...
1
vote
1answer
58 views

prime division problem

$a,b,c \in$ {0,1,2,...,9} with at least one of $a,b,c$ nonzero. Prove that the six-digit integer $abcabc$ is divisible by at least 3 distinct primes. My thinking is not to use induction as there is ...
0
votes
1answer
44 views

fundamental theorem of arithmetic problem

Change machine contains n quarters, 2n nickels, 4n dimes, n positive integer. Find all values of n so that these coins total k dollars, k positive integer. My thinking is to reduce coins to prime ...
3
votes
2answers
70 views

prove/verify prime division

$a_i$ positive integers for $1\le i\le n$ if $p$ prime and $p\mid a_1a_2\cdots a_n$ then $p\mid a_i$ for some $1\le i\le n$: My thinking is to prove it by contraposition. $p$ does not divide ...
2
votes
2answers
39 views

Proof: no fractions that can't be written in lowest term with Well Ordering Principle

My question is the exact same question as the one in this post but I commented on it but it's from a year ago so I just wanted to bump it and see if I could get a response: Prove that there's no ...
0
votes
0answers
28 views

Bézout's identity Application

I am trying to prove the following lemma: Let $n,m$ be positive integers, and let $d = GCD(m,n)$. Let $c,r$ be positive integers s.t. $d = cm - rn$ If $c > dn $, then for every two positive ...
2
votes
1answer
68 views

Introductory Induction Proof

I am in currently in a discrete mathematics class, and I've done well on every problem I've encountered. Unfortunately, I find myself weak at some of the seemingly straight forward induction problems. ...
1
vote
1answer
26 views

Expanding Base 2B representation of an integer

Consider an integer$L$ written in Base 2B which digits $$a_n a_{n-1} a_{n-2} ... a_1 B$$ Where $a_i$ are arbitrary constants such that $9 \le a_i < 2B$. I am attempting to prove that the square ...
2
votes
3answers
146 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 ...
1
vote
1answer
51 views

Proving something about the Game Nim

I was reading Elementary Number Theory and Its Applications by Rosen wherein I came across the problem (located on Page 31 summarized below) Consider the Game Nim. In this game there exist a finite ...
1
vote
3answers
70 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$ ...
0
votes
1answer
35 views

Maximum value of function involving factorials

Define $$g_{(k,j)} = \frac{a^{n-k}b^k(k+n)!x^{k+n-j}}{k!(n-k)!(k+n-j)!}$$, where $n,k,j \in \Bbb{N}$ are fixed such that $(0 \leq x \leq a/b ),(b<a),(0 \leq k \leq n ),(2 \leq j \leq 2n),(0 \leq ...
2
votes
1answer
32 views

The number of distinct multiples of composites greater than $n$ that can be factored into two naturals less than or equal to $n$

Given a list of composites between $n$ and $\lfloor \frac{n^2}{2} \rfloor$: What would be the most efficient way to count, for each composite, the number of its distinct multiples that can be ...
0
votes
0answers
21 views

How to find a certain uppper bound (see details)?

What would be the most efficient way to find this upper bound? Given natural number n and a natural number d < n, find the ...
0
votes
0answers
28 views

Mathematical Modeling for the Mapping Relationship

I have encountered a problem in my research and have no idea how to model the problem. To simplify the description, I tell a game with the same rule instead of the original problem. Consider two set ...
3
votes
5answers
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 ...
0
votes
1answer
43 views

How to derive this formula about the bracket function?

Is there a direct way of proving that $$ [nx] = [x] + [x+\frac{1}{2}] + [x+\frac{1}{3}] + \ldots + [x+ \frac{1}{n}]$$ for each real number $x$ and for each positive integer $n$? My effort: Let ...
1
vote
2answers
56 views

Factor $n=59305397$ given that $ p-q \le 10 $

So what is given is that $n=pq\ ; \ p-q = \sqrt{(p+q)^2 -4n}$ Rearranging the $p-q$ equation, I get $$ p+q = \sqrt{(p-q)^2 +4n}$$ So, $$2p = (p+q) + (p-q) \ \text{and} \ q=\cfrac{n}{p}$$ However ...
0
votes
1answer
59 views

Polynomial producing only primes

The polynomial: $$a_n x^{n}+a_{n-1}x^{n-1}+\dots+a_{1}x+a_{0}$$ Coefficients ai are natural numbers, the claim is once you substitute the positive integers 1,2,3,... for $x$ the values of the ...
1
vote
1answer
33 views

A relationship among multiple periodic arrays

There are N periodic arrays ai[n] with period Ti, respectively, where i=1, 2, … , N. Each array has a property that a[n]=1 when n=k*T where k is integer, otherwise a[n]=0. Then a new array is created ...
0
votes
2answers
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 ...
-1
votes
1answer
35 views

$p>3$ prime, show that there exists $0<x,y<\sqrt{p}$ so that $p$ divides $cx-y$

Let $p>3$ be a prime number that does not divide $c$. Show that if $p>3$ there exists $x$ and $y$ with $0<x,y<\sqrt{p}$, such that p divides $cx-y$. I believe I've shown the above but for ...
7
votes
4answers
10k views

What five odd integers have a sum of $30$?

I've been asked the following question: What five odd integers from the set $\{1, 3, 5, 7, 9, 11, 13, 15\}$ that when summed together equals to $30$? Note that any integer can be used more than ...
1
vote
1answer
56 views

Number Theory Related Question: 3x^10=10x^3(mod13)

Number theory related question. Give all answers to: $$3x^{10}\equiv 10x^3 \pmod{13}$$ $0$ is obvious but I can't see a good way to draw out $12$. I've got this so far: Rearrange to ...
2
votes
1answer
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 ...
23
votes
2answers
959 views

A fascinating number chain.

Take a two digit number $10x+y$ of which both digits are different. now add $y-x$ to this number. By repeating this process you will get a chain of numbers $45,46,48,52,49,54,53,51,47,50.$ after $50, ...
4
votes
3answers
597 views

Prove that every prime larger than $3$ gives a remainder of $1$ or $5$ if divided by $6$

Can we prove that every prime larger than $3$ gives a remainder of $1$ or $5$ if divided by $6$ and if so, which formulas can be used while proving?
6
votes
3answers
82 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 ...
0
votes
0answers
31 views

Miller-Rabin primality test and testing one

I'm learning about Miller-Rabin primality test but in all the problems I see in the notes of a person I got them from, I see that even if he expressed the number as $2^1 \cdot something$, he still ...
0
votes
0answers
25 views

Taking the modulus of the power?

So I'm learning about Euler's theorem for reducing large powers modulo $n$ and what I'm wondering about is: can we simply take the modulus of a power of a number the same way we take it of the number ...
0
votes
1answer
18 views

Prove that all elements in the set T is divisible by 3 using structural induction.

Let T be the set defined recursively as follows: (1) (0,3) $\in$ T (2) If (x, y) $\in$ T, then (x + 2, y - 1) $\in$ T and (x - 3, y) $\in$ T. (3) Every element of T can be obtained from (1) by ...
0
votes
2answers
50 views

Find the smallest possible integer $k$ such that $8|7^{348}+2^{5605}+k$

$$ \text{Find the smallest possible integer } k \text{ such that } \\ 7^{348}+2^{5605} +k \text{ which is divisible by } 8 \text{ given that } $$ a≡b mod n⇒a^m≡b^m mod n okay, I understand that $a ...
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$
1
vote
4answers
147 views

What's the easiest way to factor $5^{10} - 1$?

What's the easiest way to factor $5^{10} - 1$? I believe $5 - 1$ is a factor based off the binomial theorem. From there I do not know. We are using congruence's in this class.
2
votes
1answer
68 views

Define a recursive sequence for the following formula f(n) = n(n+1)

Define a recursive sequence for the following formula f(n) = n(n+1). Preferably one only defined by previous $a_n$ terms, i.e., no 'n' terms. If possible that is. So for example the following ...
0
votes
1answer
37 views

Help with understanding Induction proofs

From my understanding, to prove induction problems, we must: Find a base case Assume n=k holds true Prove n=k+1 with the assumption However I am looking at the proof of a problem and they don't ...
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
72 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 ...
2
votes
2answers
134 views

Prove that if $a$ is irrational then $\sqrt a$ is irrational

Just hints but solution thx. Any hints for me? I simply suppose that $a = \dfrac mn$ then $\sqrt a = \sqrt{\dfrac mn}$ But this does not make sense ..
3
votes
1answer
47 views

$k$th difference of $1,2^k,3^k,…$

I read, in an exposition of Euler's proof of Fermat's theorem on sums of squares, that the $k$-th order finite forward difference of the function $f(x_i)=x_i^k$, relatively to the nodes $x_i=i$ where ...
0
votes
2answers
101 views

decoding an encrypted text with modulo

A B C D E F G H I J K L M N O 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 P Q R S T U V W X Y Z Ä Ö Ü ß 16 17 18 19 20 21 22 23 24 25 26 27 28 29 00 A encryption method ...
0
votes
1answer
84 views

Prove or disprove the following statement. $7 \ | \ (x^3 + x^2 + x + 2)$, where $x$ is an odd integer

We're learning about modulus and division (Discrete mathematics and proofs course). I'm not exactly sure how to tackle this sort of problem, is there some sort of property of cubic functions ...
0
votes
1answer
35 views

showing that encryption method is bijective

A encryption method relates a letter Ω to letter $Δ\equiv aΩ + d$ $(mod 30)$ with $a, d\in {\Bbb N}$. Each letter relates to a number: A = 01, B = 02, C = 03 ... i. Show, that this encryption method ...
0
votes
3answers
120 views

Greatest common divisor. Help [closed]

Let $n \in \mathbb{N}$. Prove that $$\gcd(2^n+7^n;2^n-7^n)=1$$ $$\gcd(2^n+5^{n+1};2^{n+1}+5^n)=3\text{ or }9$$
1
vote
8answers
226 views

How to find all the positive integral solutions of $5x+7y=100$?

How to find the number of all the positive integral solutions and the solutions itselves of $$5x+7y=100?$$ Please help me!!
1
vote
1answer
42 views

Sum of floor of rational product

Given natural numbers $a,b,n$, where $a<b$, $n<b-1$, and $a$ and $b$ coprime, Find a closed form for the sum: ${\displaystyle \sum_{k=1}^n \left\lfloor k \frac{a}{b} \right\rfloor}$ We know ...
12
votes
5answers
307 views

How many prime numbers are there in between $1000!+1$ and $1000!+1000$, inclusive?

I know $1000!$ is not a prime number as any number $1000$ or less is a divisor, but how would I know if $1000!+1$ is prime? Any hints? Also, use the above question to prove that you can find $n$ ...
0
votes
5answers
81 views

$4011x+42053 \equiv 2x-782398 \pmod {10}$

$4011x+42053 \equiv 2x-782398 \pmod {10}$ $10|(4011x+42053-2x+782398) \space \rightarrow \space 10|(4009x + 824451)$ $\rightarrow\space 4009x\equiv -824451 \pmod {10}$ I am dubious about this next ...
2
votes
4answers
55 views

Find the smallest positive $n$ such that $n! \equiv 0 \pmod {425}$

By exhaustion I found $n=17$, but in trying to solve this I can only see that: $$425\space |\space n!\space \longrightarrow\space 425k=n!$$ Any hints?