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

learn more… | top users | synonyms (1)

3
votes
0answers
63 views

Multiple of $n$ and the sum of its digits is $k\geq n$.

Show that for every positive integers $k\geq n$, with $n$ not divisible by $3$, there is a positive integer divisible by $n$ and such that the sum of his digits is $k$.
0
votes
1answer
29 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
59 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
5
votes
3answers
572 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,2,3,5,7,11,13,17,19,23,29,31,37,39,41,43,...
0
votes
3answers
51 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
31 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
896 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. ...
4
votes
1answer
74 views

Solve $x^4 - 2x^3 + x = y^4 + 3y^2 + y \wedge (x,y) \in \mathbb{Z}^2$

I want to solve equation $x^4 - 2x^3 + x = y^4 + 3y^2 + y$ in integers. The task comes from the LXVI Polish Mathematical Olympiad. Series with this task ended twenty days ago, so it is legal to talk ...
0
votes
2answers
34 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.
2
votes
2answers
102 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
32 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 \text{...
2
votes
0answers
61 views

Convergent sum of reciprocals?

Let n denote a positive integer and let $\sigma(n)$ denote the sum of all divisors of $n$, so that $\sigma(n)$ is larger than $n$ (for $n > 1$) but not by much since it's bounded above by $c\ ...
3
votes
1answer
103 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 ...
10
votes
0answers
224 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
35 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
145 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) ...
19
votes
2answers
556 views

Does this system of simultaneous Pell-like 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
164 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 $(...
2
votes
2answers
183 views

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

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 ...
1
vote
1answer
339 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
81 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}$. ...
2
votes
2answers
94 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 $n\...
6
votes
1answer
76 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 \...
1
vote
0answers
59 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 ...
-1
votes
2answers
35 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 these:...
2
votes
0answers
41 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 $a\...
1
vote
5answers
141 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
50 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
518 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
2answers
28 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}$$?
3
votes
2answers
110 views

Prove $-1$ and $1$ are the only units in $\mathbb{Z}$

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
135 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 ...
2
votes
3answers
461 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
67 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 - false....
2
votes
1answer
70 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
48 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 $...
2
votes
1answer
41 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
44 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 ...
3
votes
3answers
2k 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 $2+(n+1)...
1
vote
2answers
378 views

How do I find all the primes that are 1 less than a perfect cube?

I need some help with the problem in the topic (find all the primes that are 1 less than a perfect cube). So far I can see that if we let $a$ be some positive integer, then we are looking for all ...
4
votes
3answers
129 views

For what $a,b$ such that $ax^2+by^2 = z^2$?

This post made me think about this question. What is the criterion on positive integer $a,b$ such that, $$ax^2+by^2 = z^2$$ can be solved in positive integers $x,y,z$? (Three broad classes are: 1) ...
1
vote
2answers
39 views

Proving one-to-one and onto

So I am learning how to prove a function is one-to-one and onto. On some of the other threads in math stackexchange I noticed a proof: Assume $f(m,n)=f(m',n')$. To show from this that $(m,n)=(m',n')$....
1
vote
5answers
189 views

What is an example of a bijective function f: Z to N that isn't piecewise?

Like without using if even or odd. Like how you can define a bijection $f\colon\mathbb{N}\to\mathbb{Z}$ by is $f(n)=\lfloor n/2\rfloor\cdot(-1)^n$.
2
votes
2answers
59 views

A question on divisibility

For what values of $x,y \in \{1,2,3,...9 \}$, does $$10x+y \space\mid 100x + y $$ ? What approach should I take for solving this problem ?
2
votes
2answers
44 views

What is $\gcd(x,x+2)$?

Show that $\gcd(x,x+2)$ is $1$ if $x$ is odd and $2$ if $x$ is even. I am looking for a much simpler proof beside the one which I have posted.
0
votes
1answer
14 views

In what case we get this relation: $a^{m}≡b^{m}(mod(c))$

Let $a,b$ and $c$ three natural numbers such that $a≡b \pmod{c}$. I am asking when getting relation $a^{m}≡b^{m}\pmod{c}$, in which $m \in \mathbb{N}$
3
votes
2answers
42 views

Reference for this theorem: $a, b$ coprime, $f(k) := ka \bmod b$, then $f$ is bijection on $\lbrace 0, …, b−1 \rbrace$.

I need to use the following theorem in a paper but have to expect that some of the audience (physicists) is not familiar with it, so I would like to reference it: Let $a$ and $b$ be two coprime ...
0
votes
1answer
51 views

Show that days with the identical calendar date in the years 1999 and 1915 fell on the same day of the week.

I think I'll be able to work this problem if I understand the question. I am having difficulty in interpreting the problem (the phrase "identical calendar date" is throwing me off). Any help is ...
2
votes
1answer
49 views

$\lambda(n^2)$ versus $n\lambda(n)$

Let $\lambda$ be the Carmichael function. What is the relationship between $\lambda(n^2)$ and $n\lambda(n)$ ? It is easy to prove that $\lambda(n^2)\le n\lambda(n)$ $\ (\star)$. Actually, $\lambda(n^...
1
vote
1answer
67 views

Maximum value of multiplicative order

Let $x \in \mathbb{Z}_{n^2}^*$ and let us assume that the multiplicative order of $x$ is multiple of $n$, then what is the maximum value of multiplicative order possible for $x$ under modulo $n^2$ ? ...