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

learn more… | top users | synonyms (1)

1
vote
5answers
72 views

Mod question: $-5 \pmod 3$?

How come $-5 \equiv 1 \pmod 3$ and not $-5 \equiv 2\ $ or $\ -2 \pmod{3}$? $-\frac{5}{3}= -1 -\frac{2}{3}$. i.e. Remainder is $-2$ or $2$?
1
vote
1answer
653 views

IMO 2015 problem 2 [duplicate]

Determine all triples $(a,b,c)$ of positive integers such that each of the numbers $$ab-c, \quad bc-a, \quad ca-b$$ is a power of $2$. (A power of $2$ is an integer of the form $2^n$, where $n$ is a ...
-7
votes
1answer
60 views

Why isn't $1/0 = \infty$, based on multiplication? [closed]

I have a doubt. In normal multiplication, if $2$ divides $10$ means the answer would be $5$ and it can be rewritten as $2*5$. Like that $1/0 = \infty$; it's obvious. Suppose, if we do as we did ...
2
votes
3answers
92 views

Can $x\pi$ be rational?

When I was solving a math test, I came across this problem - Let $x$ be an irrational number. What type of number is $x\pi$? a) Rational only b) Irrational only c) Could be rational ...
3
votes
3answers
58 views

Using the Well ordering Principal to prove a property of integers

Use the Well ordering Principle for the integers to prove that given any integer $n>0$ there exists an integer $m$ and a non negative integer $k$ such that $n=3^{k}.m$ and $3$ is not a divisor of ...
5
votes
2answers
53 views

Floor Function Equation

How many positive integers $ N$ less than $ 1000$ are there such that the equation $ x^{\lfloor x\rfloor} = N$ has a solution for $ x$? (The notation $ \lfloor x\rfloor$ denotes the greatest ...
5
votes
2answers
363 views

Are there any two triangular numbers that add up to a perfect cube?

The triangular numbers are all of these numbers: $$\sum_{n=1}^x n$$ For $x\gt 0$ and that $x$ are only integers. Here's a list: $$1,3,6,10,15\cdots$$ Are there any $2$ triangular numbers in which ...
1
vote
3answers
83 views

Find numbers $\overline{abcd}$ so that $\overline{abcd}+\overline{bcd}+\overline{cd}+d+1=\overline{dcba}$

Find the numbers $\overline{abcd}$, with digits not null that satisfy the equality \begin{equation}\overline{abcd}+\overline{bcd}+\overline{cd}+d+1=\overline{dcba}\end{equation} where ...
2
votes
3answers
58 views

Problem in proof of Chinese remainder theorem, and applying it.

Please don't mark it as duplicate. First read the whole question. So Chinese Remainder Theorem states that,: Let $n_1,n_2,...,n_k$ be $k$ positive integers which are pairwise relatively prime. If ...
-1
votes
2answers
32 views

If$x \equiv y\pmod n$ then prove that $(x,n)=(y,n)$ [closed]

Given: $x \equiv y\pmod n$ To prove:$(x,n)=(y,n)$ where, $(a,b)$ means HCF/GCD of both $a$ and $b$. I don't know where to start the solution of the problem, please guide me in the right direction.
2
votes
1answer
57 views

3 Questions on number theory.

We have to everything using number congruences, and I am just a beginner, I know a few theorems, and we have to solve these using basics. 1) If $n=a^4$ where $a \in \mathbb Z$ then prove that $n ...
0
votes
2answers
55 views
0
votes
2answers
22 views

Proving the greatest common divisor (number theory)

Prove that for all $a, b, c \in \mathbb N$ $\gcd(a,bc)=1~~~$ if and only if $~~~\gcd(a,b)=\gcd(a,c)=1$ $$~$$ What I tried **1)**$~~~\gcd(a,bc)=1 \implies \gcd(a,b)=\gcd(a,c)=1$ ...
0
votes
3answers
108 views

Find all positive integers for the following question [closed]

Find all positive integers that makes the result of $$\frac{1}{x}+\frac{1}{y}$$ integers
2
votes
2answers
67 views

Relatively prime to $42$ and $70$

How many numbers are relatively prime to $42$ and $70$? There's no set limit (i.e. numbers relatively prime must be less than $42$ or $70$), so I'm unsure how to figure this out. I think I'm ...
2
votes
3answers
34 views

Question on a passage from “Rational Points on Elliptic Curves”

I was reading the book "Rational Points on Elliptic Curves", when I've crossed with the following passage: "(...) since $3$ does not divide the order $p-1$ (where $p$ is a prime) of the cyclic group ...
-3
votes
1answer
49 views

Example of a diophantine polynomial

A diophantine set is a subset of a power $\mathbb{Z}^k$ of the set $\mathbb{Z}$ of integers which can be written as $$\{x \in \mathbb{Z}^k : \exists y \in \mathbb{Z}^m : P(x, y)=0\}$$ where $P$ is a ...
1
vote
1answer
28 views

How do you prove that rational points on $y^2 = x^3 - 2$ are of the form $(A/B^2, C/B^3)$, where are $A, B, C$ are coprime?

I was only browsing this book on number theory and the author shows how the solution $(3, 5)$ can be used to generate other exotic rational solutions and then in the end leaves the problem I'm asking ...
4
votes
4answers
51 views

How many four digit numbers are perfect square whose first and last two digits are same?

I tried it by assuming the number as $\sqrt{1100a+11b}$ and than tried to find figure out perfect square but I am unable to approach further.
5
votes
1answer
229 views

Conjectured compositeness tests for $N=k\cdot 2^n \pm 1$ and $N=k\cdot 2^n \pm 3$

How to prove these conjectures ? Definition : $\text{Let}~ P_m(x)=2^{-m}\cdot \left(\left(x-\sqrt{x^2-4}\right)^{m}+\left(x+\sqrt{x^2-4}\right)^{m}\right)~ , \text{where}~ m ~\text{and}~ x ~\text{are ...
-1
votes
0answers
31 views

Using the Euclidean algorithm to prove the greatest common divisor (number theory)

Use the Euclidean algorithm to prove the following theorem If $gcd (a,b)= d $, then $gcd (a,-b) =d$. What i tried This means $gcd (a,b)= gcd (a,-b) =d$ $a=dx$, $b=dy_{1}$, $-b=dy_{2}$ Hence ...
1
vote
1answer
53 views

Using the Well Ordering Principle to prove the first principle of mathematical induction

Theorem (The Well Ordering Principle): A least element exists in any non empty set of positive integers. Use the Well Ordering Principle to prove the first principle of mathematical ...
1
vote
0answers
51 views

Proving that the g.c.d of non-consectuive Fibonnaci numbers is also a Fibonacci number

I'm trying to prove that: for non-consecutive Fibonacci numbers, and I know that consecutive Fibonacci numbers are co prime, but I just don't how to prove this using what I know. **EDIT: Lulu has ...
6
votes
1answer
101 views

Prove for $2p +1$ divides $2^p + 1$

The following theorem is well known and already proven by Lagrange 1775 Let $p = 3$ (mod $4$) be prime. $2p+1$ is also prime if and only if $2p+1$ divides $2^p - 1$. But how can we prove this: Let ...
0
votes
2answers
52 views

Why is it true that if $ax+by=d$ then $\gcd(a,b)$ divides $d$?

Can someone help me understand this statement: If $ax+by=d$ then $\gcd(a,b)$ divides $d$. Bezout's identity states that: the greatest common divisor $d$ is the smallest positive integer that ...
2
votes
1answer
56 views

Solutions of $(2x-1)^x\equiv1\mod\ p$ [closed]

Has the equation $(2x-1)^x\equiv 1\mod{p}$, for $p=1+6qx$, where $p$, $q$ are primes, $x$ is an odd integer and $x<p$ any solutions except $x=1$? Many thanks.
1
vote
4answers
37 views

If $n$ people are placed in a room, prove that at least $2$ of those people will have the same number of friends in the room.

If $n$ people are placed in a room, then at least $2$ of those people will have the same number of friends in the room. I want to prove this statement. Here are some of my thoughts: If all the ...
1
vote
1answer
39 views

How to use the division algorithm to prove these form of integers?

I have in my notes the form of the integers as: Now, I know that I have to use the division algorithim to prove the first form, and I can do this, but in the second form of an integer $4k$ isn't the ...
3
votes
1answer
37 views

Question regarding number congruences?

First of all, before the question, I want to clear that how does $17x \equiv 1 \pmod 4 $ imply $x \equiv 1 \pmod 4$? I did: $17x \equiv 1 \pmod 4 $ $16x \equiv 0 \pmod 4$ Subtracting both, We ...
1
vote
2answers
45 views

Application of Euler's theorem apart from finding last digits of huge numbers

I am looking for clever applications of Euler's Theorem. On browsing the internet, I see that nearly all the applications of the theorem asks for finding last few digits of a huge number. The only ...
0
votes
2answers
62 views

Is the integer $0$ a deficient number?

It is well known that the divisors of the integer $0$ are all non zero-integers numbers ,the sum of those divisors greater than $0$, then is it a deficient number ? Thank you for any help
6
votes
1answer
41 views

Median order of an element in an additive group modulo $n$

I'm trying to gain some intuition here. Suppose we have the group $\mathbb{Z}_{n}$ (with the operation being addition modulo $n$). What is the median order of an element of this group when $n$ is a ...
3
votes
1answer
38 views

Help understand theorem that any set of first order sentences satisfied by N has a model that's a strict superset of N.

I saw the following theorem (in Computational Complexity book by Papadimitriou, p. 111) : Theorem : If $\Delta$ is a set of first-order sentences such that $N$ $\vDash \Delta$, then there ...
1
vote
1answer
24 views

A congruence for the prime counting function in Wolfram.What does it actually say?

I saw today in functions.wolfram.com a congruence for the prime counting function which says $\binom {2prime(k)-1} {prime(k)-1} \pmod{prime(k)^3}=1$ (the third congruence at the bottom). What does ...
2
votes
2answers
32 views

Using a sieve and Mertens' theorem to show a formula for $\pi(x)$ - Does this work?

When I was younger, just starting highschool, I loved tinkering with prime sieves. I still have notes that I took. I had written down that $$\pi(x)\sim x\prod_{n=1}^m\frac{p_n-1}{p_n}+m-1.$$ ...
7
votes
1answer
81 views

Is the set $\phi(\mathbb{N})$ syndetic?

A set $A \subset \mathbb{N}$ is said to be syndetic if the gaps in $A$ are bounded. Is the set $\phi(\mathbb{N})$ syndetic? (where $\phi$ denotes de Euler totient function) I've thought quite a ...
2
votes
1answer
25 views

Is there a necessary form of consecutive composites?

For every $n \geq 3$ there is a tuple of $n-1$ consecutive composites, namely the composites of the form $n! + 2, \dots, n!+n$. However, must a tuple of $n$ consecutive composites take the form? It ...
-1
votes
0answers
29 views

Values of the Sudan function

I am talking about the first discovered recursive function which is not primitive recursive. I would like to know the exact values of $\ f(3,3,3), f(2,0,4), f(2,7,1), f(2,3,2)$ (where $f$ is the ...
1
vote
0answers
39 views

Possible maps $(\mathbb Z[i]/\mathfrak p)^\times\to\mu_4$

Let $\mathfrak p$ be a maximal ideal of $\mathbb Z[i]$ not dividing 2. Is it true that the only maps from the cyclic group $(\mathbb Z[i]/\mathfrak p)^\times$ the the fourth roots of unity are powers ...
0
votes
1answer
28 views

Proof of decimal expansion [duplicate]

If the denominator of a rational number contains only 2 and 5 as prime factors then the decimal expansion of the rational number is terminating. How can I Prove this
4
votes
1answer
205 views

How do I prove that there is no other :$k=9,12,18$ for which this fails :$\sigma^k(114) \equiv 0\mod 6 $?

let $\sigma(n)$ be the sum of divisors for a positive integer for example : $$\sigma(6)=1+2+3+6=12$$ . I have performed some calculations in wolfram alpha about the sum divisors of this number: ...
0
votes
0answers
18 views

Determining recurring decimal expansion

Is it possible to determine if the decimal expansion of a rational number is recurring or terminating by looking at the denominator, without actual division
0
votes
2answers
34 views

Showing that these two definitions of $\gcd(a,b)$ are equivalent

So far I have encountered with two definitions of the GCD of $a$ and $b$. The first definition is: $\gcd(a,b)$ is an integer that has the following properties: $d>0$ $d\mid a$ and ...
0
votes
0answers
30 views

Number Theory by Andreescu and Andrica Problem 1.6.2 Solution

Problem 1.6.2 in Number Theory by Andreescu and Andrica is taken from 1997 Czech and Slovak Mathematical Olympiad, and is stated as follows: "Show that there exists an increasing sequence $\{a_n\}$ ...
0
votes
1answer
34 views

What is the probability of occurence of natural numbers?

Suppose that humankind had a ∞-ary number system so that no psychologically distinguished numbers like 1000, 250, or 333 existed. What is the probability of a number n ∈ ℕ (including 0) to occur when ...
1
vote
0answers
80 views

Taking partial sums repeatedly to get to perfect powers.

Let $S_{1,k}(n) = n,\ S_{i,k}(n) = \sum_{\text{n terms},(k-i+2)\nmid j} S_{i-1,k}(j)$ For example, $S_{1,2}(n) = n, S_{2,2}(n) = 1 + 3 + \dots+(2n-1) = n^2$ With $k=3$, take partial sums avoiding ...
0
votes
1answer
20 views

Are these partial sums and partial products absolutely convergent?

For arbitrary $m \in \mathbb{N},$ $$\sum_{n=1}^{m}\ \sum_{d | \#_n}\mu(d)=\sum_{n=1}^{m}\big | \sum_{d | \#_n}\mu(d)\ \big |\ = \ 0,$$ $$\prod_{n=1}^{m}\ \prod_{d | \#_n}d^{\mu(d)}=\prod_{n=1}^{m}\big ...
2
votes
3answers
54 views

Change of radix without using radix 10

If one has a number in radix $b$: $(d_nd_{n-1}\ldots d_0)_b$, and wants to change to radix $p$, how could one achieve that without passing from $b$ to $10$ and then from $10$ to $p$? I thought I had ...
3
votes
1answer
52 views

Solve $2b(b-1) = t(t-1)$ as Pell's equation

I know the method of continued fractions to solve the Pell's equation. I need help turning $2b(b-1) = t(t-1)$, with $b, t$ as integers, into the form $x^2 - ny^2 = 1$, if possible. This is a Project ...
4
votes
2answers
69 views

If for almost all $p \equiv 1$ (mod a) it holds that $p \equiv 1$ (mod m), then…

Let $a,m\in \mathbb N$ Suppose that for almost all primes $p \equiv 1$ (mod a) we have that $p \equiv 1$ (mod m) Can we say something about $a$ and $m$? For example $m$ divides $a$ or vice versa? I ...