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

learn more… | top users | synonyms (1)

3
votes
1answer
146 views

Fermat solved $x^2+2=y^3$ by infinite descent? [duplicate]

In a letter to Christiaan Huygens entitled "on problems in the theory of numbers: a letter to Christiaan Huygens", Fermat claism that he solved the diophantine $x^2+2=y^3$ using infinite descent. Here ...
0
votes
0answers
37 views

Cross relations on number

I have problems finding a method to solve the following problem: Given three relative numbers $p_{1}$, $p_{2}$, $p_{3}$ and three positive numbers $q_{1}$, $q_{2}$, $q_{3}$ we have the following ...
0
votes
2answers
349 views

Use the Euclidean algorithm to prove that gcd(na, nb) = n gcd(a, b).

Assume that a,b,n are all natural numbers. I was going to set it up as: na = q(1)*n(b) + r(1) where a>b and go down the chain: nb = q2 * r(1) + (r2) but something seems off. Someone told me ...
1
vote
1answer
62 views

Use Fundamental Theorem of Arithmetic to prove that if $a >1$, $p$ is prime, and $p|a ^n$ for some $n \in \mathbb{N}$, then $p|a$

So, by the FTOA, since $a >1$, then a can be broken down into a product of a prime factors, so $a = p_1 \times p_2 \times \dotsm \times p_k$. Then, can I say that since $a$ is multiplied by itself $...
0
votes
2answers
247 views

Assume that 495 divides the integer 273x49y5 where x,y ∈ {0,1,2…9}. Find x and y.

So, I know that $495 = 5\times 9\times 11$. So then, if that's the case, then the number $\overline{273x49y5}$ must be divisible by $495$ if and only if it is divisible by 5 and 9 and 11. Then, I ...
1
vote
1answer
71 views

If $x^3 =7$, then $x$ is irrational

Assuming there is a real number $x$ with $ x^3 =7$, prove that $x$ is irrational. I started the proof by contradiction, and I got to the point that $7q^3 = p^3$, but I don't know what should I do ...
0
votes
2answers
59 views

what is the easiest way to show $-1$ is quadratic residue modulo $p=4k+1$?

what is the easiest way to show $-1$ is quadratic residue modulo prime $p=4k+1$? Is there a better way than showing $(2k)!^2\equiv -1 \mod p$?
0
votes
4answers
85 views

Reducing primes in $\mathbb Z[i]$

Let $4k+1=p$ be a prime. Assume you do not know $p=a^2+b^2$(this is what we intend to prove). Over $\mathbb Z[i]$, how does one prove that $p$ splits into conjugates? That is, if $p = (a+bi)(c+di)$,...
1
vote
1answer
45 views

Verify proof that ${p \choose r} ≡ 0 \pmod p$

Let $p$ be a prime number. For any $1 ≤ r ≤ p − 1$, prove that $${p \choose r} ≡ 0 \pmod p$$ I'm thinking that it suffices to show $p$ divides ${p \choose r}$. So then: $$\begin{align} p\ |\ {p \...
3
votes
2answers
54 views

Math for Computer Science

I have a couple of questions on the material in "Mathematics for Computer Science" by Eric Lehman and Tom Leighton. Q1. This is a theorem in the book: Theorem 24. Let $p$ be a prime. If $p|a_1a_2 ...
2
votes
2answers
35 views

If $d$ is a natural number and $d^2$ divides $y^2$ then does $d$ divide $y$?

If $d$ and $y$ are positive integers and I know that $d^{2}|2y^{2}$ then $d^2|2$ (i.e $d=1$) or $d^2|y^2$ . In the case that $d^2|y^2$ does that imply that $d|y$ for all $d,y$ ? Thank you.
1
vote
3answers
106 views

If $x^2$ is divisible by $4$ then $x$ is even?

I am studying discrete mathematics as course and I have to prove this "If $x^2$ is divisible by $4$ then $x$ is even". I am wondering how to prove it using the contrapositive of this ...
0
votes
2answers
36 views

finding the largest term in a binary summation

I'm working on a problem that involves the following summation: $$y=\sum_{i=0}^{x}i2^i$$ I need to determine the largest value of $x$ such that $y$ is less than or equal to some integer K. Currently I'...
0
votes
1answer
26 views

Rings with zero-divisors

this might be an odd question but I know that in a ring with no zero-divisors $ac|bc$ implies $a|b$, if $c\neq 0$. So are there Rings with zero divisors where $ac|bc$ still implies $a|b$? Thank you.
2
votes
1answer
93 views

Conjecture on sum of powers

Let $n$ be an odd number, $x,y$ integers and $p$ a prime number. Now, suppose that $p\ne n$ and $$ p|\frac{x^n+y^n}{x+y} $$ Then, I have been observed that $p \equiv 1 \pmod{n}$. This is, all of the ...
0
votes
1answer
24 views

Would someone please explain this argument? (Legendre formula)

Here is an argument in my book. Theorem If $n$ is a positive integer and $p$ is a prime, then the exponent of the highest power of p that divides $n!$ is $\sum_{k=1}^\infty [\frac{n}{p^k}]$ ...
1
vote
2answers
79 views

Prime numbers and $\sqrt{10301}$

On my exam recently, we had the following question: Use the prime number theorem to estimate the number of primes less than $\sqrt{10301}$, and hence, give a concise argument whether 10301 is prime ...
5
votes
4answers
168 views

Find the continued fraction of the square root of a given integer [duplicate]

How to find the continued fraction of $\sqrt{n}$, for an integer $n$? I saw a site where they explained it, but it required a calculator. Is it possible to do it without a calculator?
2
votes
1answer
184 views

The greatest common divisor is the smallest positive linear combination

How to prove the following theorems about gcd? Theorem 1: Let $a$ and $b$ be nonzero integers. Then the smallest positive linear combination of $a$ and $b$ is a common divisor of $a$ and $b$. ...
2
votes
2answers
109 views

Triplets of distinct integers > 1 that return integer values.

If $(A, B, C)$ are distinct integers $> 1$, and $$f(A, B, C) = \frac{\frac{A^2-1}{A} + \frac{B^2-1}{B}}{\frac{C^2-1}{C}},$$ then for what (if any) triplets $(A, B, C)$ is $f(A, B, C)$ an integer? ...
1
vote
2answers
318 views

Open/closeness of subsets of natural numbers

So I've just started reading about neighbourhood and Hausdorff space. It makes me wonder if $(\mathbb{N},\mathcal{P}(\mathbb{N}))$ is Hausdorff and why, and are sets in $\mathbb{N}$ open or closed or?
2
votes
3answers
78 views

How to prove that $\gcd(2n+3, 3n+1)$ divides $7$?

How can I start proving that gcd(2n+3, 3n+1) | 7? EDIT: It is $\gcd(2n+3, 3n+1)$ divides $7$. My bad. Thanks paw88789.
0
votes
2answers
46 views

If a is not relatively prime to n prove modulo property

If $n>1$ is integer and $1\le a \le n$ is integer such that $(a,n)\neq 1$ then prove there exist integer $1 \le b <n $ such that $ab \equiv 0(mod \; n)$ I have tried everything from going to ...
1
vote
0answers
58 views

Generalization of Hensel's lemma

I've been trying to prove the following generalization of Hensel's lemma: Let $ f\in \mathbb{Z}[x_1, \dots, x_n] $ and $ f=0 $ be a diophantine equation. Let's assume that for some $ d \in \mathbb{N}...
0
votes
1answer
38 views

Find out $f(n)$ where n is an integer

Suppose I need a function $f(n)$ such that $f(n)$ is odd when $n=4,12,20,28...$ and even when $n=8,16,24,32...$. Then the answer would be $f(n)=\frac{n}{4}$. Similarly, now suppose I need $f(n)$ such ...
5
votes
1answer
4k views

The square root of a prime number is irrational

If $p$ is a prime number, then $\sqrt{p}$ is irrational. I know that this question has been asked but I just want to make sure that my method is clear. My method is as follows: Let us assume ...
12
votes
2answers
202 views

Integer solutions of $x^3-x+9=5y^2$

What are the solutions in integers of $x^3-x+9=5y^2$? [Source: Hungarian competition problem]
1
vote
1answer
52 views

About primitive roots.

Assuming $6$ is a primitive root mod $p$ ( for some odd prime $p$) ( assuming this is possible) then could $p$ have another distinct primitive root $n$ (such that $1 \lt n \lt (p-1)$) where $(6,n) = 1$...
2
votes
2answers
166 views

How to find all cyclic quadrilaterals with integer sides?

We need to find all cyclic quadrilaterals (or formulas that gives its sides), which have integer sides $a,b,c,d$. The constrain is that its area must be an integer multiple of its perimeter. We can ...
0
votes
1answer
32 views

If $a\pmod 3 \equiv 1$ and $b\pmod 3 \equiv 2$, then $ab \pmod 3 \equiv 2$

I'm stuck on this this problem: Let $a$ and $b$ be positive integers with $a\pmod 3 \equiv 1$ and $b\pmod 3 \equiv 2$. Prove that $ab \pmod 3 \equiv 2$. I think the first step for the direct ...
1
vote
2answers
44 views

figure out $f(n)$ under given conditions

Suppose I need a function $f(n)$ such that $f(n)$ is odd when $n=4,12,20,28...$ and even when $n=8,16,24,32...$. Then the answer would be $f(n)=\frac{n}{4}$. Similarly, now suppose I need $f(n)$ such ...
2
votes
6answers
325 views

Proving the irrationality of $\sqrt{5}$: if $5$ divides $x^2$, then $5$ divides $x$

I am working on proving that $\sqrt{5}$ is irrational. I think I have the proof down, there is just one part I am stuck on. How do I prove that $x^2$ is divisible by 5 then $x$ is also divisible ...
2
votes
0answers
31 views

find other sums similarly under sum

In the under sum there exists all number 1,...,9. Similarly write at least 10 sums other. $$659+214=873.$$ For example we can write $259+614=873$ or $619+254=873$ or $596+142=738$. Do there exists a ...
2
votes
4answers
292 views

How to find the $n$th term of a repeating pattern

What is the nth term of following sequence $1,2,3,4,5,6,1,2,3,4,5,6,\ldots$ $(n, n+1, n+2, n+3,\ldots,$ $,n+p, n, n+1, n+2, n+3,$ $n+4, n+5,$ $\ldots,$ $n+p,$ $n,$ $n+1,$ $\ldots)$ Actually, I am ...
4
votes
4answers
140 views

Prove that $2^{10}+5^{12}$ is composite

Prove that $2^{10}+5^{12}$ is composite I need to solve this using only high school mathematics. Any ideas?
9
votes
5answers
230 views

$2^{50} < 3^{32}$ using elementary number theory

How would you prove; without big calculations that involve calculator, program or log table; or calculus that $2^{50} < 3^{32}$ using elementary number theory only? If it helps you: $2^{50} ...
0
votes
4answers
78 views

Proving $\gcd(a,b) = ax+by \Rightarrow \gcd(x,y) = 1$

I'm not entirely sure of how I should prove this statement: $$ \gcd(a,b) = ax+by \Rightarrow \gcd(x,y) = 1 $$ So I've tried $$ \begin{align} &\gcd(x,y) = d \Rightarrow x =x'd, y=y'd\\ \...
2
votes
3answers
177 views

$\dfrac1a+\dfrac1b=\dfrac1c$, $a, b, c \in \mathbb{N}$ with no common factor, find all solutions [duplicate]

Given $\dfrac1a+\dfrac1b=\dfrac1c$, where $a, b, c \in \mathbb{N}$ with no common factor, find all solutions. Actually, you can think this question as a follow up of this one. Today, I saw this ...
1
vote
1answer
114 views

problem about Euler function $\phi$.

For a positive $m$, let $\phi(m)$ denotes the number of integers $k$ such that $1\leq k\leq m$ and $GCD(k,m)=1.$ Then which are necessarily true? (1) $\phi(n)$ divides $n$ for all $n>0$ (2) $n$ ...
1
vote
1answer
110 views

Using Extended Euclidean Algorithm for $85$ and $45$

Apply the Extended Euclidean Algorithm of back-substitution to find the value of $\gcd(85, 45)$ and to express $\gcd(85, 45)$ in the form $85x + 45y$ for a pair of integers $x$ and $y$. I have no ...
0
votes
1answer
18 views

Solving a congruence — where to start?

For which positive integers $n$ is it true that $$1^2 + 2^2 + \cdots + (n − 1)^2 \equiv 0 \,(\text{mod } n)$$ I have no idea where to start. I'm just looking for a nudge in the right direction. Any ...
-1
votes
2answers
83 views

Why multiplication should be a secondary binary operation?

Isn't every multiplication resumed in a simpler summing operation? For instance: $5 \times 2 = 5 + 5$; or $5 \times 1/2 = 1/2 + 1/2 + 1/2 + 1/2 + 1/2$; or $1/2 \times 1/2 = 1 \times 1/4 = 1/4$. Why ...
2
votes
1answer
59 views

The congruence has a solution

Sentence: If $a \in \mathbb{Z}$, then the congruence $x^2=a \pmod p, \forall p \in P$ has a solution $\Leftrightarrow$ $a=\square$ in $\mathbb{Z}$. If $a=\square$, then $\exists d \in \mathbb{Z}$ ...
4
votes
2answers
58 views

$(n+1)^{\textrm{st}}$ prime less than $2^{2^n}$

Using elementary means, show that the $(n+1)^{\textrm{st}}$ prime is less than $2^{2^n}$ please do not use fancier stuff like the prime number theorem or beyond. using this how can you show that $\pi(...
0
votes
1answer
32 views

Divisibility Test Question of Curisosity

Why do we only do divisibility tests up to 11? At least, in my proofs class and in my textbook, that's all it goes up to: 11. Can anyone explain?
1
vote
2answers
66 views

Elementary Number Theory: Divisibility proof

Let $k,m,n \in N\setminus \{0\}$, s.t. $n=k\cdot m$. Show that $k$ is odd $\Rightarrow ∀ a,b \in Z: (a^m+b^m) \mid (a^n+b^n)$ In the first part of the task, I have already shown that $∀ a,b \in Z: (...
3
votes
2answers
70 views

The Mersenne number $2^{83}-1$ is not prime

There is a solved example on my textbook (in Portuguese) showing that the Mersenne number $2^{83}-1$ is not prime.He says: We have $2^{8}=256\equiv 89\mod 167$ $2^{16}\equiv 72 \mod 167$ $2^{32}\...
6
votes
1answer
567 views

If $m^n = n^m$, why does $m$ to be a factor of $n$?

Let $m^n = n^m$ with $n,m \in \mathbb{N}$ and $n > m.$ Why does $m$ have to be a factor of $n$? I think it's because of the prime factorization, but I can't prove it.
10
votes
2answers
177 views

Triplets satisfying $(a^3+b)(b^3+a)=2^c$

Find the number of triplets $(a,b,c)$ satisfying $(a^3+b)(b^3+a)=2^c$, where $a,b,c\in \mathbb{N}$ A trivial solution is $(1,1,2)$. I think there aren't any other such triplets, so I've been ...
0
votes
1answer
49 views

Calulus on the set of natural numbers

Can we think about Calculus on $\mathbf{N}$? How would work the notion of neighborhood, limit, continuity and differentiability and analyticity? I need these to understand discrete dynamics over $\...