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

learn more… | top users | synonyms (1)

2
votes
2answers
46 views

Wilson's theorem

According to Wilson's theorem, when p is prime (p-1)! mod p = -1 or p-1 What's the remainder in cases of (p-2)! mod p or ...
-5
votes
1answer
44 views

Proof - a | b and b | a then a = b [closed]

For all integers a and b, if a | b and b | a, a = b. Can something think of a proof? I have done this: Proof: Suppose m and n are integers such that m|n and n|m, but n ≠ m. Let m = 1 and n = ...
2
votes
1answer
77 views

Show that $1$ and $-1$ are the only divisors of $1$

I have this from my textbook. I do understand the proof in depth, I also see the logic of how they cancel out all options to eventually show that the statements us true. My problem is the tiny thing ...
10
votes
0answers
108 views

If $n^x\in\Bbb Z,$ for every $n\in\Bbb Z^+,$ then $x\in\Bbb Z$ [duplicate]

Let $x$ is a real number such that $n^x\in\Bbb Z,$ for every positive integer $n.$ Prove that $x$ is an integer. I got that problem here and it looks difficult, I tried writing $x$ as $\lfloor ...
3
votes
1answer
67 views

Period of Fibonacci mod $b$?

It is not too difficult to show that the Fibonacci numbers mod $b$ form a periodic sequence. I would like to say something interesting about the period. There is a small shortcut to the brute-force ...
2
votes
0answers
24 views

Expected value of Reversed Addition

A recent CodeGolf question defines "reverse addition" for two integers $a, b$ as follows: do normal "grade-school" addition, but from left-to-right (with leading zeroes as necessary) instead of ...
0
votes
1answer
44 views

How do I show $1$ is not a trivial odd perfect number?

This question related to my this question in MO ,some comments stated that the integer $1$ is trivial answer for this question ,but here i'm very confused when we say that the sum divisors of $1$ is ...
1
vote
2answers
28 views

If $p\equiv1\pmod{4}$ is a prime, then $-4$ and $(p-1)/4$ are both quadratic residues of $p$.

I'm working on the following problem: If $p\equiv1\pmod{4}$ is a prime, then $-4$ and $(p-1)/4$ are both quadratic residues of $p$. This means it must be shown that $(-4/p)=1$ and ...
-2
votes
0answers
38 views

Using Well Ordering Principle to prove a definition of an integer

Use the well ordering principle to prove that an integer $n$ is even if there is some integer $k$ such that $n=2k$.( I know there is easier ways to prove this, but for the sake of practising, i use ...
2
votes
1answer
105 views

Prove that $\sqrt 3$ is irrational [duplicate]

I have to prove that $\sqrt 3$ is irrational. let us assume that $\sqrt 3$ is rational. This means for some distinct integers $p$ and $q$ having no common factor other than 1, $$\frac{p}{q} = ...
0
votes
2answers
50 views

Can I solve for all integer solutions of this diophantine equation?

I do not know much about this subject, but this problem is bothering me. $$ x + 33y = 2399 $$ How can I find the possible integer values of x and y? I know there are two solutions, which I ...
2
votes
2answers
53 views

Is it possible to determine the number divisors of n! especially for large n?

I read this paper by P. Erdos, page 2. I didn't understand it. How do I determine the number divisors of $n!$ ? I'd like an example application, for example if I want to determine the number divisors ...
3
votes
5answers
88 views

How many $5$ element sets can be made?

Let $m$ be the number of five-element subsets that can be chosen from the set of the first $14$ natural numbers so that at least two of the five numbers are consecutive. Find the remainder when $m$ ...
3
votes
3answers
56 views

Double Factorial Sum

Let $ n!!$ to be $ n(n-2)(n-4)\ldots3\cdot1$ for odd $ n$ values and let $ n(n-2)(n-4)\ldots4\cdot2$ for even $ n$ values. Also let $ \displaystyle \sum_{n=1}^{2009} \frac{(2n-1)!!}{(2n)!!}$ be ...
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
661 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
59 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
109 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
50 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
230 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 ...