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

learn more… | top users | synonyms (1)

0
votes
0answers
55 views

Pillai equation solvability

I would like to learn an elementary method of solving Pillai equation. The equation $a^x-b^y = c$ has at most two solutions for $(x, y)$ in $\mathbb{Z} $, where $a$ and $b$ are greater than or equal ...
1
vote
2answers
52 views

Is $a^{p^n-1}=1\mod p$ where $p$ is prime number and $1<a<p-1$?

Is $a^{p^n-1}=1\mod p$ where $p$ is prime number and $1\lt a\lt p-1$? When $n=1$ by little fermats theorem theorem it is true. But i can't justify generaly whether it is correct or not. But when i ...
4
votes
5answers
126 views

Show that $\gcd(a,b)>1$

Given are three natural numbers $a$, $b$ and $c$, for which $$\frac1a+\frac1b=\frac1c,$$ show that $\gcd(a,b)>1$. Could you someone provide a hint? I already tried algebraic manipulation, but ...
0
votes
1answer
32 views

Implications of a prime square dividing a binary quadratic form

Let $u,v$ be positive integers with $\gcd(u,v)=1$, let $k\ge 3$ be an odd integer, and fix a prime $p$. Now what are the implications of $p^2 \mid (u^2+kv^2)$? I know implications in certain cases, ...
1
vote
4answers
134 views

How to find the last non-zero digit of $50!$

A week ago i made a similar question but nobody help me, i´ve been trying but i still don't get it. I want to know how to find the last non-zero digit of $50!$. my try: First i have to know how ...
0
votes
2answers
57 views

Complete this reasoning? Number theory

I have this really weird confusion with $gcds$ and and basic theory dividing numbers and at the moment, I am stuck at this. If $gcd(a,b) = 1$, it means the biggest number that divides them evenly ...
0
votes
1answer
252 views

if ca ≡ cb mod n and d = (c,n) where n = dm . prove that a ≡ b mod m

if $ca \equiv cb \ (\textrm{mod}\ n)$ and d = (c,n) where n = dm , prove that $a \equiv b \ (\textrm{mod}\ m)$ so here is my attempt from $ca \equiv cb \ (\textrm{mod}\ n)$ we know that n | ca - ...
3
votes
2answers
1k views

Prove by contradiction that $\forall x,y \in \Bbb Z: x^2-4y \ne 2$

Prove that for all $x,y \in \mathbb{Z}$, $x^2 - 4y \ne 2$. Using a contradictory method would be appropriate. So, for this question, I assume, for the sake of a contradiction, that There exists ...
0
votes
2answers
236 views

A New, Possible Proof of the Infinitude of the Primes?

$$1=1$$ $$2=2$$ $$3=3$$ $4=2\cdot2$ At $4$, the first prime number, $2$, is there as a factor. So I say that at the square of $2$, $2$ comes into play as a prime factor. At this point, $2$ is the ...
3
votes
1answer
45 views

Bibinomial coefficient integer

For integers $n \ge k \ge 0$ we define the bibinomial coefficient. $\left( \binom{n}{k} \right)$ by $$ \left( \binom{n}{k} \right) = \frac{n!!}{k!!(n-k)!!} .$$ What are all pairs $(n,k)$ of integers ...
2
votes
2answers
133 views

Proof that $\sqrt{4}\notin\mathbb{Q}$ of course wrong but where is the flaw?

Assume $$\eqalign{ \sqrt{4}\in\mathbb{Q}&\Longrightarrow(\exists a,b\in\mathbb{Z})\sqrt{4}=\frac{a}{b}\text{ and }\gcd(a,b)=1\\ &\Longrightarrow 4b^2=a^2\Longrightarrow a\text{ is even}\\ ...
3
votes
0answers
121 views

finding all integers for which 23 is a quadratic residue

Some time ago I have solved an exercise and now, re-reading it, I don't understand a step. I ask your help in that. I will take some results for granted, although in the original exercise they were ...
1
vote
3answers
64 views

Are there any nonzero integers $a$ , $b$ such that $a^2$ = $3b^2$

I know since 3 is prime then nothing divides 3 except 3 and also 3 is a factor for only multiples of 3. $a^2$ must be a multiple of 3. But I am kinda stuck here.
0
votes
1answer
63 views

If a number is divisible by two others, then it's divisible by their lcm

Prove that if $c$ is a common multiple of $a$ and $b$, then $c$ is a multiple of $\operatorname{lcm}(a,b)$ Nobody in my class has found a way to do it. Whatever I try, I always come to the ...
2
votes
1answer
54 views

Is it true that if $\gcd(a,b) = 1$ and $\gcd(a,c) = 1$ then $\gcd(ac,b) = 1$?

Is it true that if $\gcd(a,b) = 1$ and $\gcd(a,c) = 1$ then $\gcd(ac,b) = 1$? I know that $\gcd(a,b) = 1$ means that there exist integers $m$ and $n$ such that $am + bn = 1$ Same thing for ...
0
votes
2answers
136 views

Is this true about the open intervals on the real line?

Let $a<b$ and let $m$ be a positive integer such that $$3^{-m} < \frac{b-a}{6}.$$ Then can we find a positive integer $k$ such that the open interval $$\left(\frac{3k+1}{3^m}, ...
5
votes
2answers
294 views

Discriminant of monic cubic function and integer roots

We all know that if the discriminant of a monic quadratic is a perfect square, then both of its roots will be integers. In my research, I'm interested in monic cubics, and I was wondering whether ...
0
votes
1answer
23 views

Finite Arithmetic Progressions - Beginning and End Points

First, I want to express the integers 27,29,31,33, and 35 in the form of a finite arithmetic progression. Second, I want to express the integers 37,39,41,43,45, and 47 in the form of a finite ...
1
vote
2answers
87 views

proportion of primes in a polynomial sequence

It is conjectured (Bunyakovsky) that when $P(x)$ is a polynomial from $\mathbb{Z}[X]$, irreducible, with positive leading coefficient and so that the integers $P(n)$ , $n\gt0$ do not share a common ...
2
votes
2answers
82 views

$n$ positive integer, then $n=\sum_{d|n} \phi(d)$ (proof Rotman's textbook)

I've just read in Rotman's group theory textbook the proof of the following statement: Statement If $n$ is a positive integer, then $$n=\sum_{d|n} \phi(d),$$ where the sum is over all divisors $d$ ...
0
votes
1answer
26 views

Proof of simple divisibility fact

If I want to prove that $a \nmid bc$, and I know that $gcd(a, b) = 1$, then why does it precisely does it suffice to show that $a \nmid c$? Thanks.
1
vote
2answers
23 views

Precise definition of congruence class?

So I'm going through Niven's The Theory of Numbers, and it gives the definition that: $$a \equiv b \pmod m \implies m \mid (a - b)$$ However, a few pages after this definition, it gives a theorem ...
2
votes
1answer
118 views

Are all transcendental numbers theoretically accessible?

I apologize if the title (and the body) of this question is worded incorrectly, but I have no real experience in (transcendental) number theory, so it's probably the best I can do. I've been thinking ...
2
votes
2answers
186 views

Proving $\phi(m)|\phi(n)$ whenever $m|n$ [duplicate]

Show that $\varphi(m)|\varphi(n) $ whenever $m|n$. I am stuck after writing the formula. I know that if $m$ divides $n$, that means one of the prime factors of $n$ would include $m$ or a multiple of ...
3
votes
2answers
126 views

Show that there exists no integer b such that f(b) is 1993.

We are given a polynomial $f$ with integer coefficients such that for 4 distinct integers $a_1,a_2,a_3$ and $ a_4$, $f(a_1)=f(a_2)=f(a_3)=f(a_4)=1991$. Show that there exists no integer $b$ such that ...
0
votes
1answer
137 views

Maximum and Minimum in Set Theory

In a group of 100 students, each student has to opt for one or more of the three subjects among Physics, Chemistry and Mathematics. The number of students who opted for Mathematics is more than the ...
6
votes
2answers
158 views

Prove that $2^n +1$ in never a perfect cube

Prove that $2^n +1$ in never a perfect cube I've been thinking about this problem, but I don't know how to do it. I know that if $m^3=2^n+1$, then $m$ should be an odd number, but I 'm not able to ...
8
votes
2answers
522 views

Novel approaches to elementary number theory and abstract algebra

As a part of a university course, I'll have to study Herstein's Topics in algebra and Hardy&Wright's Introduction to the theory of numbers. Can you suggest some books (to be used as companions) ...
1
vote
3answers
707 views

Prove that if $x$ and $y$ are rational numbers and $y\ne 0$, then $x/y$ is a rational number [duplicate]

Prove that if $x$ and $y$ are rational numbers and $y\ne 0$, then $\frac{x}{y}$ is a rational number. How do I prove this, and also which proving method would I use? I'm confused between that and ...
2
votes
0answers
150 views

Is Legendre’s solution of the general quadratic equation the only one?

Legendre famously solved the general quadratic equation $$ ax^2+bxy+cy^2+dx+ey+f=0 $$ by noting that \begin{equation*} 4a(b^2-4ac)(ax^2+bxy+cy^2+dx+ey+f) = 0 \tag{$\star$} \end{equation*} along with ...
0
votes
3answers
56 views

Whether the given number is divisible by 24?

Let $a$ be an integer which is not divisible by 2 and 3. Prove that 24 divides $a^2-1$. This, $a$ can be written as $a=2x+1$ or $a=3z+r$ where $r=1,2$ and $x$ and $z$ are integers. This $a^2-1= ...
2
votes
3answers
303 views

Non-linear diophantine equation

Let $k$ and $n$ be positive integers and $y(n-x)=(k+nx)$. What is the condition of $k$ and $n$ such that there exist positive integers $x, y$ as the solution of $y(n-x)=(k+nx)$?
2
votes
1answer
88 views

Proof concerning specific class of Proth numbers

Is this proof acceptable ? Theorem Let $N = k\cdot 2^n+1$ with $n>1$ , $k<2^n$ , $k$ odd and $3 \nmid k $ , thus $N$ is prime iff $3^{\frac{N-1}{2}} \equiv -1 \pmod N$ Proof Necessity ...
1
vote
1answer
22 views

Typical problem on P with conditions

I am looking for prime $p$ greater than or equal to $3$ such that $p|y^2 + 4$ as well as $4|p-3$. I need simple discussion to conclude the existence of $p$. Thanks again.
5
votes
5answers
2k views

Prime number between $n$ and $n!+1$

I am trying to prove that ($\forall \ n\in\mathbb{N}$) there exists a prime number $q$ such that $n < q \le 1 + n!$ I have made a graph with $n=0$ through $n=10$ and found solutions to all of them ...
0
votes
1answer
38 views

$f(x)=x^3+ax^2+bx+p=0$ has no integral solutions.

let $p$ be a prime number, does the polynomial:$f(x)=x^3+ax^2+bx+p=0$ have any integral solution if $p>a>2$ and $ x>2 $? I concluded that there was none on the basis that $p>a$ and a ...
1
vote
0answers
35 views

Let$\ H$ be a hyperinteger. If$\ f(n)=g(n)$ is true for all$\ n \in \mathbb{N}$, will it be so for all$\ H$?

I do know that all true first order statements in$\ \mathbb{N}$ are also valid in$\ \mathbb{N^*}$, so for example$\ \sin(H \pi) =0$. As a consequence, my question is equivalent to: is$\ f(n)=g(n)$ a ...
1
vote
2answers
107 views

Proof: $2^{2^t}-1$ is divisible by at least $t$ distinct primes

A question into the elementary number theory. Proof: $2^{2^{t}}-1$ is divisible by at least $t$ distinct primes. My ideas about the issue are the following: Distinct primes, call them: ...
-2
votes
1answer
40 views

Question on the relationship of a quantity and its value modulo n [closed]

Is it correct to say that if there are 13 chameleons, then there are $1\pmod 3$ chameleons? If so, why?
0
votes
1answer
189 views

Upper bound for the prime gap above $n$

Imagine each natural number as a point in space along a path on which one can stand and walk. Imagine standing at any one point and looking forward toward the next prime. If we stand at $1$ and look ...
4
votes
2answers
77 views

Co-prime Number

As my knowledge, if there are only two numbers and their there GCD is 1, then they will be relatively coprime , so 10 and 4, they are not relatively co-prime, cause their GCD is 2. Am I right? ...
2
votes
0answers
316 views

Differences Between Multiples of Consecutive Odd Primes

For each pair of consecutive odd prime numbers, regardless of the difference between them, there will be points on the whole number line where the two odd primes are factors of a pair of numbers that ...
2
votes
1answer
57 views

Simple polynomial factorization

If $f(x) = x^3 + (a-5)$, where $a$ is some integer. Find all the possibility of an integer $a$, such that $f(x)$ can be factorized. I did one example: If $ a = 4$, then $f(x) = x^3 -1$ and $x^3-1 = ...
0
votes
1answer
93 views

Why do we add 6 in BDC addition.

When performing addition to BCD, if we get an invalid BCD, we remedy this by adding a binary $6$ to our sum. Example: $0101 + 0110 = 1011$ (Invalid in BCD) So, we add $6$ to fix this. $1011 + 0110 ...
1
vote
1answer
78 views

What is the meaning of $\mathbb N_0^n$?

If I have a function defined as , $U_{n} = \{(x_{1},x_{2},...,x_{n}) \in \mathbb{N}_{0}^{n} | x_{1} + 2x_{2} + 3x_{3} + ... + nx_{n} = n\}$ what is the meaning of having $\mathbb{N}_{0}^{n}$ raised ...
0
votes
1answer
57 views

Fast modular exponentiation

Suppose that $p$ and $q$ are distinct primes, then for every integer $a$ and exponent $e$ with $e\not \equiv (\bmod \,(p - 1)(q - 1))$ show that: ${a^e} \equiv {a^{e\, \cdot \,\bmod \,(p - 1)(q - ...
0
votes
1answer
31 views

Restatement of a result on the gcd of two integers.

I read the following statememt: Let $(a, b) \in \mathbb Z^2$. An integer is the sum of a multiple of $a$ and a multiple of $b$ if and only if it is a multiple of their gcd which we denote ...
1
vote
2answers
73 views

Progressions With Squares

In an arithmetic progression like $3+5n$, what happens when we square $n$ and rewrite the progression as $3+(5 n^2)$? It is no longer arithmetic, right? What do we call this kind of progression? Does ...
0
votes
3answers
113 views

The smallest positive integer that can be written in the form $72x+40y$

What is the smallest positive integer that can be written in the form $72x+40y$ where $x,y\in\mathbb{Z}$.I think it might be the greatest common divisor of it, but I am not sure if it is right.
0
votes
1answer
84 views

Why does the borrowing method for subtracting stop working if the bottom number is bigger?

My brother was given the problem $2.3-4$, and tried to solve it using the standard one over the other format. $.3-.0=.3, 2-4=-2$, answer is $-2.3$. He looks at the answer in the back and sees that it ...