# Tagged Questions

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

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$.
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 ...
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
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,... 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)$? 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$... 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. ... 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 ... 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. 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: ... 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{... 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\ ... 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 ... 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 ... 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 ... 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) ... 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? 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 (... 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 ... 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 equationAx+By+Cz=D$$where A,B,C,D\in \mathbb Z and the range for x,y,z\in \mathbb ... 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}. ... 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\... 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 \... 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 ... 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:... 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\... 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 ... 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 ... 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 ... 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}$$? 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. 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 ... 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 ... 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.... 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 ... 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 ... 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? 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 ... 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)... 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 ... 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) ... 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').... 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. 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 ? 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. 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}$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 ... 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 ... 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^...
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$ ? ...