Questions on congruences, linear diophantine equations, greatest common divisor, divisibility, etc.

learn more… | top users | synonyms (1)

0
votes
3answers
54 views

How to find all square solutions?

Given the equation $f(k) = 4-7k $ what is the easiest way to find which integer values of $k$ makes $f(k)$ a perfect square $(-3, -11, ...)$ (I hope for something better than just testing values of ...
1
vote
1answer
133 views

A polynomial is called a Fermat's polynomial…

A polynomial is called a Fermat polynomial if it can be written as the sum of the squares of two polynomials with integer coefficients. Suppose that $f(x)$ is a Fermat polynomial such that $f(0) = ...
1
vote
1answer
101 views

$n \mid k^2 \land n+1 \mid l^3 \land n+2 \mid m^4 \to n=?$

Find three consecutive integers such that the first is divisible by a square, the second one is divisible by a cubic and the third is divisible by a fourth power.
3
votes
1answer
367 views

Show that if $a$ and $b$ are positive integers then $(a, b) = (a + b, [a, b])$.

Show that if $a$ and $b$ are positive integers then $(a, b)=(a + b, [a, b])$. I was thinking that since $[a, b]=LCM(a, b)=\frac{ab}{(a, b)}$ that if $d= (a + b, [a, b])$, then $d|[a,b]$ and thus ...
2
votes
5answers
2k views

How many numbers must be selected from the set

How many numbers must be selected from the set {1, 3, 5, 7, 9, 11, 13, 15 } to guarantee that at least one pair of these numbers add up to 16, explain your answer?
0
votes
3answers
620 views

Show that if a, b and c are integers with c|ab then c|(a,c)(b,c)

Show that if a, b and c are integers with c|ab then c|(a,c)(b,c) Now (a, c) and (b, c) would both divide c since it's the gcd, but how would I show c divides their product, and (a,c)(b, c) $>=$ c ...
7
votes
10answers
4k views

Prove by induction that $5^n - 1$ is divisible by $4$.

Prove by induction that $5^n - 1$ is divisible by $4$. How should I use induction in this problem. Do you have any hints for solving this problem? Thank you so much.
0
votes
1answer
246 views

Show that if $a$ and $b$ are positive integers then there are divisors $c$ of $a$ and $d$ of $b$ with $(c, d) = 1$ and $cd = [a, b]$

Show that if $a$ and $b$ are positive integers then there are divisors $c$ of $a$ and $d$ of $b$ with $(c, d) = 1$ and $cd = [a, b]$ Since $a$ and $b$ are positive, surely both will have a prime ...
2
votes
1answer
35 views

Salvage of a given propostion

Consider the statement: For all integers $r$, $s$, and $a$, and natural numbers $m$, if $ra \equiv sa \pmod m$ then $r\equiv s \pmod m$. I have found this statement to be false by the counterexample ...
3
votes
2answers
120 views

2 is a primitive root mod $3^h$ for any positive integer $h$

It's easy to verify that 2 is a primitive root mod $3^2$. But then why does it follow that 2 is a primitive root mod $3^h$ for any positive integer $h$? This was used in the solution of 2009 Putnam ...
4
votes
2answers
117 views

A curious product formula

Fiddling with Mathematica seems to suggest the following: $$\frac{(2^2)(4^2)(6^2)\cdots(2N^2)}{(1^2)(3^2)(5^2)\cdots(2N-1)^2}=N\pi+\frac{\pi}{4}+\frac{\pi}{32N}-\frac{\pi}{128N^2}+o(1/N^2).$$ Does ...
2
votes
2answers
47 views

Is $20+k^2\not\equiv4(\text{mod}~7)$ for all $k\geq0$?

I've been asked to explain why during quadratic probing in a hash function it is possible that a collision resolution is never found (eg. empty spots exist in the hash table, but the quadratic probing ...
1
vote
0answers
36 views

In a translation of a classic math book: is the term *normal* translated correctly? Is there a better term?

I am reading an English translation of the classic book by Gelfond & Linnik: Elementary Methods in the Analytic Theory of Numbers. Here is the definition of "normal" from the book (page 5 in my ...
2
votes
1answer
264 views

Show that any set of 7 distinct integers includes two integers $x$ and $y$, such that either $x-y$ or $x+y$ is divisible by 10

Show that any set of 7 distinct integers includes two integers $x$ and $y$, such that either $x-y$ or $x+y$ is divisible by 10. I'm trying to apply the pigeonhole principle, but haven't been able to ...
-1
votes
4answers
264 views

all prime numbers have irrational square roots [duplicate]

How can I prove that all prime numbers have irrational square roots? My work so far: suppose that a prime p = a*a then p is divisible by a. Contradiction. Did I begin correctly? How to continue?
1
vote
1answer
93 views

Solving $[x]+[x]=[2x]$

Solving the equation $[x]+[x]=[2x]$ Since $[x]$ is the greatest integer function. I tried, $\forall x\in\mathbb{N}$, we have $[x]=x$ and $[2x]=2x$ this implies that $[x]+[x]=[2x]$, but if ...
2
votes
2answers
411 views

Sum of the reciprocals of divisors of a perfect number is $2$?

How do I show that the sum of the reciprocals of divisors of a perfect number is $2$? I tried $d_i\mid n$ with $i\in\mathbb{N},\;d_i\leq n$ then ...
3
votes
3answers
307 views

Prove that $n$ divides $\phi(a^n -1)$ where $a, n$ are positive integer without using concepts of abstract algebra

I need to show that $n$ divides $\phi(a^n -1)$ where $a, n$ are positive integer without using concepts of abstract algebra I know that $$a^n\equiv 1\pmod {a^n-1}$$ How do i proceed from there?
1
vote
1answer
41 views

Prove that $\left(\frac2p\right) = 1$ if $p \equiv 1,7 \pmod 8$ and $\left(\frac2p\right) = -1$ if $p \equiv 3,5 \pmod 8$ using ring theory

Let $p$ be an odd prime number and let $\alpha = [X] \in R=\mathbb F_p[X]/\langle X^4+1\rangle$, and $y = \alpha + \alpha^{-1}$ I've proven: 1) $\alpha$ is a primitive eight root of unity in $R$. ...
0
votes
2answers
63 views

Ratio and proportion

I was solving some maths problems when I got this one. I tried it several times in different ways but i didn't get any solution If(a + b): (b + c) : (c + a) = 6 : 7 :8 and a + b + c = 14, then find ...
0
votes
3answers
259 views

Word problem on divisibility

I came across the following word problem related to divisibility: In a certain town 2/3 of the adult men are married to 3/5 of the adult women. Assume that all marriages are monogamous (no one is ...
0
votes
2answers
50 views

How to derive $2^k-1$ from $2^{k-1}+2^{k-2}+…+2^{k-k}$

Let $k\in N$, I have series of additions $2^{k-1}+2^{k-2}+...+2^{k-k}$. From trial and error I got it equal to $2^k-1$ but I am failing to understand how to derive it. For example $2^{k-1}$ will make ...
0
votes
1answer
385 views

Proving number of digits d to represent integer n in base B?

I am interested in learning about proofs for discrete mathematics. One recurring fact I find in the literature is that the number of digits $d$ required to represent integer $N$ in base $B$ is ...
1
vote
2answers
112 views

Confusion in proof that primes p=4k+1 are uniquely the sums of two squares.

I'm reading a proof in my number theory textbook that all primes of the form $p = 4k+1$ are uniquely the sum of two squares. I'm stuck right at the beginning of the proof, where they say: To ...
10
votes
2answers
132 views

Let $a_k=\frac1{\binom{n}k}$, $b_k=2^{k-n}$. Compute $\sum_{k=1}^n\frac{a_k-b_k}k$

Let $a_k=\frac1{\binom{n}k}$, $b_k=2^{k-n}$. Compute $$\sum_{k=1}^n\frac{a_k-b_k}k$$ By computing some partial sums, the answers are 0. It seems an inductive argument is possible.
2
votes
1answer
29 views

Reasoning about Schnirelmann Density: Proving that $d(C) \ge d(A) + d(B)$

I am taking this argument from Gelfond & Linnik's Elementary Methods in the Analytic Theory of Numbers. They state if for every $n \ge 1$, there exists $m \in [1,n]$ where $C(n) - C(n-m) \ge ...
0
votes
3answers
45 views

If s=∅ , T≠∅ then SxT = ∅ . Why? [duplicate]

I recently studied about Cartesian products and I thought that I understood its concept, Until I ran into this expression: If $S=\emptyset$, $\ne\emptyset$, then $S\times T = \emptyset$ . Is an ...
1
vote
1answer
70 views

Finite Continued Fraction Proof

Let $\alpha = \left[a_0, a_1, a_2,\cdots,a_n\right]$ be a finite continued fraction with $a_0 > 0$ and let $C_i = p_i/q_i$ be the convergent of $\alpha$. If $i\ge 1$, prove that ...
2
votes
3answers
91 views

Prove by contradiction that $(a + b + 1) ^ {\frac {1} {a + b}} $ is irrational

Suppose if it is rational: $9 ^ {\frac {1} {8}} = {\frac {m} {n}}$ I know what to do with relative primes. M and N are the relative primes. $(n \times 9 ^ {\frac {1} {8}}) = m $ $(n \times 9 ^ ...
1
vote
0answers
47 views

Is it correct? $\lim_{n\rightarrow \infty} \frac{c^{n}}{n!^{\frac{1}{k}}}$

This is what we have $$\lim_{n\rightarrow\infty} \frac{c^{n}}{n!^{\frac{1}{k}}},$$ $$n \in N, k>0, c>0$$ If n->inf ...
1
vote
1answer
62 views

If $gcd(m,n)=1$, prove that $u_{n}u_{m}$ divides $u_{mn}$ for all $m,n \geq 1$.

If $gcd(m,n)=1$, prove that $u_{n}u_{m}$ divides $u_{mn}$ for all $m,n \geq 1$. $u_{1}=u_{2}=1$, $u_{n}=u_{n-1}+u_{n-2}$ for $n \geq 3$
1
vote
0answers
66 views

Find all rational solutions to $x^3 - y^2 = 2$. [duplicate]

Find all rational solutions to $x^3 - y^2 = 2$. The only integers solutions are $(3,\pm5)$: http://mathforum.org/library/drmath/view/51569.html
1
vote
1answer
68 views

If n > 3 and (n + 1) is a square, is there any n that is a prime?

I am looking at properties of squares and came about this property. I am investigating the difference of squares in relation to primes.
0
votes
4answers
73 views

$d\mid n\Longrightarrow d\leq\sqrt n$

$d\mid n\Longrightarrow d\leq n$ Ok, but need to go further, I can say (if yes, how to demonstrate) that $$d\mid n\Longrightarrow d\leq\sqrt n$$
1
vote
1answer
43 views

Number of quadratic residues

I wouId like to prove that for an odd prime power $p^k$, there are $\frac{\phi(p^k)}{2}$ quadratic residues. What I have done is that if $u_1$ is a unit, so is $-u_1$, which means it is somewhere in ...
1
vote
2answers
80 views

$x^2=37\pmod {77}$ is there solution for $x$?

Is there solution for $x$? $$x^2=37\pmod {77}$$ Which method should we use, Diophant equations or? I found nothing by using induction. thanks
-1
votes
5answers
166 views

Solve for $m\in\mathbb{N}$ the equation $\phi (m)=12$

Solve for $m\in\mathbb{N}$ the equation $\phi (m)=12$ I found (by trial) $m=\{13,21,26,28,36\}$, but do not know if misinterpreted the problem, but actually I suppose I have to find an equation ...
1
vote
2answers
40 views

Why this map preserves order?

How to prove that $f:N→\{1,1+1,1+1+1,...\}$ where 1 is an identity element of ordered field, is order-preserving? I guess that maybe property if $a < b$ then $a + c < b + c$ can be useful, but ...
1
vote
1answer
135 views

For what values of m does the equation 35530x + 355y = m have integer solutions?

For what values of $m$ does the equation $35530x + 355y = m$ have integer solutions? (only find the $m$'s for which solutions exist)
2
votes
1answer
61 views

(i).Prove that $\pi_m(n)=\pi_m(n-m)+\pi_{m-1}(n)$ without using the generating functions for $\pi_m(n)$.

Questions: $\pi_m(n)$ is defined as the number of partitions of n in which each part is no larger than m. (i).Prove that $\pi_m(n)=\pi_m(n-m)+\pi_{m-1}(n)$ without using the generating functions for ...
9
votes
2answers
125 views

if such$\sqrt{37}+\sqrt{47}<\dfrac{n}{m}<\sqrt{41}+\sqrt{43}$ Find this $m$ minimum

let $m,n\in N^{+}$, if such $$\sqrt{37}+\sqrt{47}<\dfrac{n}{m}<\sqrt{41}+\sqrt{43}$$ Find the $m$ minimum the value My try: since $$(\sqrt{37}+\sqrt{47})m<n<(\sqrt{43}+\sqrt{41})m$$ ...
2
votes
3answers
73 views

Prove that if $n^{2} - \left(n - 2\right)^{2}$ is not divisible by $8$ then $n$ is even

Let $n$ be an integer. Prove that if $n^{2} -\left(n - 2\right)^{2}$ is not divisible by $8$ then $n$ is even. Can anyone help me step by step to understand this?
0
votes
1answer
162 views

Prove or disprove the following proposition

Prove or disprove the following proposition: There are no positive integers $x$ and $y$ such that $$x^2 - 3xy + 2y^2 = 10$$
9
votes
1answer
214 views

A congruence in the number of certain ternary strings

Let $a_n$ be the number of ternary strings of length $n$ which do not contain three consecutive symbols that are all different. That is, $$a_n = \Bigl|\bigl\{\,(b_k)_{1\leq k\leq n}\in ...
1
vote
4answers
3k views

Square number that is the sum of two squares in two different ways.

I would like to know if a square number exists that can be expressed as the sum of two other square numbers in more than one different way. Also only natural numbers and excluding zero.
3
votes
3answers
82 views

Prove that for all $n\in\mathbb{N}$, $\frac{s(n)}{d(n)}\geq \sqrt n$

Prove that for all $n\in\mathbb{N}$ $$\frac{s(n)}{d(n)}\geq \sqrt n$$ where $s(n) = \sum_{d|n} d$ and $d(n) = \sum_{d|n} 1$. Being honest, study some time arithmetic functions, and can not ...
0
votes
6answers
176 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
3answers
327 views

The gcd of $p+q$ and $p-q$ where $p4 and $q$ are distinct odd primes

Suppose $p$ and $q$ are distinct odd primes. Prove that $\gcd(p+q, p-q) = 2$. I had figured out that $d$ divides $2p$ and $d$ divides $2q$, but I did not recognize to use coprimeness and ...
4
votes
2answers
115 views

Show that $p!$ and $(p - 1)! - 1$ are relatively prime

If $p$ is prime number, with $p>3$ Show that $p!$ and $(p - 1)! - 1$ are relatively prime. I tried $\text{gcd}\;(p!,(p-1)!-1)=d\Longrightarrow d\mid p!$ e $d\mid(p-1)!-1$ having ...
2
votes
1answer
106 views

the sequence 1,11,111,.. and primes

Consider the sequence $\{A_n\} = 1,\, 11,\, 111,\, 1111,\, \dots\,$, where $$A_n = \displaystyle\sum\limits_{k=0}^{n} 10^k$$ I wonder if there exists an $z \in \mathbb{Z}$, such that for all ...