Tagged Questions

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

learn more… | top users | synonyms

7
votes
1answer
89 views

Checking a possible proof of Fermat's Last Theorem

Theorem 1.2 of Bennett and Skinner (Canad. J. Math., 2004) asserts that the Diophantine equation $x^{p} - 4y^{p} = z^{2}$ is unsolvable for every prime $p \geq 7.$ The following is a possible proof ...
3
votes
2answers
31 views

GCD Direct Proof

I need to show that if $a,b,c$ are ints such that $\gcd(a,b) = 1$ and $c|(a+b)$, then $\gcd(c,a) = \gcd(c,b) = 1$ I want to try and prove this directly because I think it will be more straightforward ...
0
votes
3answers
32 views

If $\gcd(a,b) = 1,$ then why is the set of invertible elements of $\mathbb Z_{ab}$ isomorphic to that of $\mathbb Z_a\times \mathbb Z_b$?

If $\gcd(a,b) = 1,$ then why is the set of invertible elements of $\mathbb Z_{ab}$ isomorphic to that of $\mathbb Z_a\times \mathbb Z_b$? I know the proof that as rings, $\mathbb Z_{ab}$ is congruent ...
2
votes
0answers
33 views

Primitive Pythagorean triple proof.

Prove that if $(x,y,z)$ is a primitive pythagorean triple with $y$ odd then there exist $u\gt v\gt0$ odd integers with $\gcd(u,v)=1$ such that $\left(\tfrac xz,\tfrac ...
1
vote
0answers
17 views

How to calculate -69^(-1) mod 1313

Which method should I use to calculate $-69^{-1} \mod 1313?$
5
votes
1answer
55 views

Last three digits in number $1^{2013} + 2^{2013} + 3^{2013} + … + 1000^{2013}$

I'm trying to find the last three digits in number $1^{2013} + 2^{2013} + 3^{2013} + ... + 1000^{2013}$. I started by calculating the remainder for even numbers, since I can present even numbers as ...
0
votes
0answers
10 views

Finding set of integer pairs for which two integer polynomials intersect

I am wondering if there is a theorem in number theory that addresses the following issue: Suppose we have two polynomials, f and g, with integer coefficients. Is there a general way to find elements ...
0
votes
1answer
17 views

Show that $\mathbb{Z} [\sqrt p]$ is an ordered Integral Domain.

Let $\mathbb{Z}[\sqrt p]=\{ a+b\sqrt p ~| a,b\in \mathbb{Z},p~is~prime\} $ Assume $\mathbb{Z}[\sqrt p]$ ia an integral domain with usual addition and multiplication. Show $\mathbb{Z}[\sqrt p]$ is an ...
0
votes
3answers
48 views

proof of divisibility of n(n+1)(2n+1) by 6 [duplicate]

How can I prove that $n(n+1)(2n+1)$ (where $n$ is a positive integer) is divisible by 6? As the product is even it is divisible by 2. But I do not know how to prove that it is divisible by 3
1
vote
2answers
34 views

Which rational primes less than 50 are also Gaussian primes?

Which rational primes less than 50 are also Gaussian primes? My attempt: First we need to list all of the rational prime numbers that are less than $50$ ...
1
vote
0answers
14 views

Number of solutions to $x^n \equiv a \pmod{2^b}$.

I've been trying to prove the following statement: Let $m \in \mathbb{N}$ and let $2^k$ be the highest power of 2 that divides $m$. Further, let $a$ be an odd integer such that $x^m \equiv a ...
0
votes
3answers
30 views

if $m>n$ prove that $ a^{2^n} + 1$ is a divisor of $a^{2^m} - 1$

Stuck on this question without much progress. Problem no 49. Section 1.2 Niven. Any hints in the right direction ? For the second part : How can I use this to find $gcd(a^{2^m}+1,a^{2^n}+1)$ ?
1
vote
0answers
18 views

Composite residuosity statement.

Consider the following definition. A number $z$ is said to be $n$-th residue modulo $n^2$ , if there exists a number $y \in \mathbb{Z}_{n^2}^*$ such that $$z\equiv y^n \mod n^2$$ Let us take $n=6$ ...
2
votes
1answer
35 views

Finding the number of divisible integers in the range $[1, 1000]$.

Sorry if this is a stupid question. I am asked to find the number of positive integers in the range $[1, 1000]$ that are divisible by $3$ and $11$ but not $9$. Here's how I $\text{tried}$ to do it. ...
0
votes
2answers
27 views

Show that for any integer not divisible by 2 or 5, there is a multiple of it which is a string of 1s. [duplicate]

Given that a number $n \equiv\{1,3,7,9\} \pmod{10} $ show that there is a multiple of $n$, $q$ that is a string of consectutive $1$s.
1
vote
1answer
37 views

$(a,b)[a,b]=ab$ in non factorial monoids

Do you know of a proof of $[a,b](a,b)=ab$ in $\mathbb Z$ that doesn't use prime factorization? To be more precise let's strip all unnecessary properties and leave only the bare bones of divisibility: ...
0
votes
2answers
19 views

$\gcd(a,n)=d$ and $s,t$ solutions to $ax\equiv b \pmod{n}$ then $s\equiv t\pmod{n/d}.$

If $\gcd(a,n)=d$ and $s,t$ are each solutions to $ax\equiv b\pmod{n}$ then $s\equiv t \pmod{n/d}$. As $d\mid a$ say $a=dm$ and as $s,t$ are each solutions, $as\equiv at\pmod{n}$ so $$a(s-t)=nk ...
0
votes
0answers
16 views

Finding the modular multiplicative inverse using Gauss's Algorithm

I have found that the inverse of 119(mod 261) is 68 by using the extended Euclidean Algorithm. But I cannot find it using Gauss's Algorithm. The fractions seem to cancel out.
2
votes
0answers
31 views

Convergent sum of reciprocals?

Let $n$ denote a positive integer and let $s(n)$ denote the sum of all divisors of $n$, so that $s(n)$ is larger than $n$ (for $n > 1$) but not by much since it's bounded above by $c\ n\log ...
0
votes
0answers
37 views

Prove $2^n \not\equiv 1 \pmod{n}$ for $n>1$ [duplicate]

Prove that $2^n \not\equiv 1 \pmod{n}$ for $n>1$. I'm asking for any advice.
0
votes
1answer
18 views

New Identities for Generalized Fibonacci Numbers?

Over the past few months I have been investigating one the generalizations of the Fibonacci numbers, called the Generalized Fibonacci Numbers (GFNs). The GFNs are just like the regular Fibonacci ...
0
votes
0answers
32 views

Proof of Gauss formula to find number of Primes

How did gauss found this formula to find the number of primes when he was 15 , can anyone provide me the proof.
5
votes
0answers
34 views

Number of ways to express a binary number in a certain way

So I'm working on a problem where I get to a point where I have to count the number of solutions to an equation or at least find a decent upper bound to be used in an estimate I need later. The ...
2
votes
0answers
20 views

Repeated application of interesting function on tuples

This question was inspired by Thursday's CIMC. Suppose you have a function $$f_n: (\Bbb{Z}/n\Bbb{Z})^n\to(\Bbb{Z}/n\Bbb{Z})^n; (a_1,a_2,a_3,\dots,a_n)\mapsto (b_1,b_2,b_3,\dots,b_n)$$ defined as ...
2
votes
3answers
116 views

Prove that $ 2^n \not \equiv 1 \pmod{n} $ for any $n > 1$.

I have proved this in following way. Assume that $ 2^n \equiv 1 \pmod{n} $. that means $n\mid(2^n -1)$. but by proof by contradiction, for $n=3$ this does not hold and we can say $n \nmid (2^n-1) ...
1
vote
0answers
34 views

Does this system of simultaneous Pell equations have any non-trivial positive integer solutions?

Let $a,b,c$ be positive integers satisfying \begin{align} 2a^2-1 &= b^2, \\ 2a^2+1 &= 3c^2. \end{align} The trivial solution is $(a,b,c)=(1,1,1)$. Are there others?
3
votes
3answers
87 views

find the last two digits of $2^{250}$.

Suppose we want the last two digits of $3^{250}$, one can use the theorem $a^{\phi(n)}\cong 1(\mod n)$ whenever $(3,n)=1$. But instead, if i have $2^{250}$, how do i solve this problem, because here ...
0
votes
0answers
23 views

$Ax+By+Cz=D \text { has a solution iff } \gcd(\gcd(A,B),C)\mid D$

I read today that $Ax+By+Cz=D \text { has a solution iff } \gcd(\gcd(A,B),C\mid D$ but I can't find it again, I also can't find any Diophantine equations with 3 variables that doesn't have solutions ...
0
votes
1answer
33 views

An effcient method of solving a Diophantine equation with 3 variables $Ax+By+Cz=D$?

I'm trying to make an efficient algorithm to find one of the solutions and how many solutions there are to the equation $$Ax+By+Cz=D$$ where $A,B,C,D\in \mathbb Z$ and the range for $x,y,z\in \mathbb ...
1
vote
2answers
32 views

Maximum GCD of two polynomials

Consider $f(n) = \gcd(1 + 3 n + 3 n^2, 1 + n^3)$ I don't know why but $f(n)$ appears to be periodic. Also $f(n)$ appears to attain a maximum value of $7$ when $n = 5 + 7*k $ for any $k \in \Bbb{Z}$. ...
1
vote
2answers
48 views

Find all solutions of the equation $n^m=x^2+py^2$ which satisfy the following properties

Prove or disprove that, There always exists a solution of the equation, $$n^m=x^2+py^2$$ with odd $x$ and $y$ and for all $m\geq k$ for some positive integral $k$. Here $p$ is an odd prime and ...
5
votes
1answer
59 views

How to solve the following equation in $\mathbb{Z}_n$?

Given an $n\in\mathbb{N}$, $a\in \mathbb{Z}_n$ and $x,y\in\mathbb{Z}$, how do I approach to solving the following equation: $a^x \equiv a^y \mod n$ I think that from here I can deduce that: $x ...
0
votes
1answer
46 views

A minimum Value Sum [on hold]

The minimum value of $\sqrt{x^4 - x^2 - 24x + 145} + \sqrt{x^4 - 23x^2 - 2x + 145}$ can be expressed in the form ($a\sqrt{b}$), where $a$ is an integer, $b$ and is not divisible by the square of any ...
1
vote
0answers
26 views

Generalization of a Diophantine Equation Problem

I've been working a lot with Pythagorean triples and sums of squares that are themselves squares, specifically interlocking sums (where one square is part of two or more sums). As part of my work I ...
0
votes
2answers
20 views

Congruence Class

I'm having a hard time with number theory, I'm being asked to determine congruence classes of inverses. I'm hoping someone could give me a step by step walkthrough of the process to solve one of ...
1
vote
0answers
25 views

$a^2+5b$ and $b^2+5a$ are perfect squares

What are all pairs of positive integers $(a,b)$ such that $a^2+5b$ and $b^2+5a$ are perfect squares? When $(a,b)=(4,4)$, both numberes are $4^2+5\cdot 4=36$, which is a perfect square. Suppose ...
1
vote
5answers
32 views

If $a, b, c ∈ \Bbb{N}$, then at least one of $a-b$, $a+c$, and $b-c$ is even

This one has been frustrating me for a while. I need to find out whether the statement is true or not true and prove it. I think it's probably true, because it came out to be for every real number ...
2
votes
1answer
21 views

Solution for congruence mod $p^2$

I've been having trouble with the following congruence, finding all primes $p$ for $$x^2 + 1 \equiv 0\ mod\ p^2$$ By the definition of quadratic reciprocity, I know that $-1$ is a quadratic residue ...
4
votes
3answers
159 views

Prove there are k consecutive non-squarefree integers

So, I've got a question for class that asks me to prove the existence of arbitrarily long runs of consecutive integers where $\mu(n)$ is zero. I've started the proof, but I need a bit of help midway ...
0
votes
0answers
13 views

Connections of results in Harmonic analysis in the theory of Transcendental Numbers

Note :This question is proposed 2 years ago in MO , I see it appropriate for stackexhange math, i posted it here as it's unsolved problem and has a connection with Transcendental Numbers , mayeb we ...
0
votes
2answers
24 views

Number theory question to establish a relation

Suppose we have $$p^2 + q^2 + r^2 +pq + qr + pr=3$$ so can we use only this relation to find $$\frac{p^2 +2q^2+r^2}{q^2}$$?
1
vote
3answers
62 views

Prove $-1$ and $1$ are the only units in $\mathbb{Z}$ [on hold]

Prove $\mathbb Z^*=\{-1,1\}.$ I have a proof, which is posted as an answer below. I'm looking for an alternate proof.
1
vote
3answers
58 views

Some questions on basic number theory

I have a number of questions related to proofs based on basic properties in number theory. While I would post them as separate questions, I feel that they are similar enough in the method that ...
1
vote
3answers
39 views

Is modular arithmetic defined for all rational numbers (with denominators coprime to modulus)?

In the expression $\frac{1}{b}\pmod m$, where $(b,m)=1$, is $\frac{1}{b}$: a) a rational number (and so rational numbers are defined in modulo arithmetic using multiplicative inverses)? b) just ...
3
votes
1answer
31 views

Finding a lower bound to the probability that a number will be shown to be composite?

Given the following method to decide whether a number $m$ is prime or not: Choose a random number $1<a<m-1$, and check whether $a^{m-1} = 1 \mod m$. If its equal, return true, otherwise - ...
1
vote
0answers
20 views

Prove a property of the divisor function (Part 2)

Further to this MSE question, I would like to pose a follow-up inquiry: If $n \in \mathbb{N}$ and $(\sigma(n) - n) \mid (n - 1)$, does it follow that $n$ and $\sigma(n)$ would have to be coprime, so ...
0
votes
1answer
26 views

Understanding Bézout's identity's proof as given on wikipedea.

I am reading this proof of Bézout's identity. It starts as: For given nonzero integers $a$ and $b$ there is a nonzero integer $ax + by$, $x$ and $y$ are also integers. The minimum absolute value of ...
1
vote
1answer
29 views

Primitive roots for a number

I want to show if a number a is a primitive root$\pmod{n}$ Is there a way to show this without raising a to all the powers between 1 and n-1?
0
votes
1answer
33 views

Proving $\lambda$ is the smallest one possible.

From this question , its proved that for all co-primes $a$ of $n(=pq)$ , $a^\lambda \equiv 1 \mod n$ where $\lambda= lcm (p-1,q-1)$ But how to prove that it is the smallest one possible . My ...
2
votes
2answers
23 views

How do I prove that for every positive integer $n$, there exist $n$ consecutive positive integers, each of which is composite?

I need help proving that for every positive integer $n$, there exist $n$ consecutive positive integers, each of which is composite. The hint that came with the problem is: Consider the numbers ...