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

learn more… | top users | synonyms (1)

10
votes
4answers
1k views

How big is a particular n!?

Is there a way to estimate how big $n!$ is for a certain $n$? For example, without using a calculator, what is the magnitude of $7!$ or $12!$ or $100!$?
0
votes
2answers
44 views

A diophantine question about squares

I have been trying to solve the following problem: Classify triples of integers $(m,n,k)$ satisfying the following equation $2mn+m+n=k^{2}$. It is very easy to obtain some solutions. However, I am ...
1
vote
1answer
138 views

What is zero times zero

What is zero zeros? What are no nothings? From a mathematical point of view it would be my thing, but none of us are educated that much in math, so I am curious to hear an expert opinion.
2
votes
2answers
131 views

Proving that repeating decimals can be rewritten as fractions without using infinite series

I'm being asked to prove that all repeating decimals can be written as fractions. The catch is that I'm not allowed to use infinite series, so that excludes most if not all methods I've seen so far. ...
0
votes
2answers
53 views

If $p~ \mid~ m^p + n^p$, prove $p~ \mid~ \frac{m^p + n^p}{m+n}$. [duplicate]

If $p \mid m^p + n^p$, and $p$ is a prime greater than $2$, prove $$p \mid \frac{m^p + n^p}{m+n}.$$ No clue how to start. Clearly $p \mid m + n$, but then what. I feel very less information is given. ...
2
votes
2answers
46 views

How do we know $ n $ is a multiple of $ 2 $ from the equation $ 2 =\frac{ n^2} { d^2} $?

My attempt at answering starts by observing that if a number $ n $ is a multiple of $ 2 $, then it can be written in the form $ n = i \cdot 2 $ where $ i $ is some integer. Now I assume that there is ...
3
votes
2answers
399 views

The sum of all possible values of N

The product $N$ of three positive integers is 6 times their sum, and one of the integers is the sum of the other two. Find the sum of all possible value of $N$. Based the given, I think the sum would ...
0
votes
2answers
44 views

Remainder question with $6!$ and 7

Find the remainder when $6!$ is divided by 7. I know that you can answer this question by computing $6! = 720$ and then using short division, but is there a way to find the remainder without using ...
3
votes
1answer
114 views

Number of 3x3 matrices with determinant $1$ and coefficients in $\mathbb{Z}_5$

Let $M=(m_{ij}), m_{ij} \in \mathbb{Z}_5$. $det(M) \in \{0,1,2,3,4\}$. There are equal number of matrices with determinants $1,2,3$ and $4$, because determinant is multiplied by $2$ when one of rows ...
1
vote
2answers
187 views

Solve $ax \equiv b \mod m$ without Linear Congruence Theorem or Euclid's Algorithm?

Origin page 5. The overhead doesn't look like Linear Congruence Theorem or anything from Euclid's Algorithm. page 4 tries to delineate ...
0
votes
2answers
64 views

Last Two digits of

How to calculate the last two digits of ${14}^{{14}^{14}}$?With the help of any method.I have tried and have got the last digit to be 6 . But not sure.
0
votes
1answer
59 views

Error in this Chinese Remainder Theorem problem with three congruence equations?

Origin - p5 - Example 5 I'm querying a possible error, thence I show the pdf as is. Is the 3 underlined in red supposed to be 2? scilicet, the last line should be $n = 2 \times 5 \times 7 $? Notation ...
0
votes
1answer
31 views

When will three cycles line up?

Three seniors $x,y$ and $z$ live in a complex and love eating pizza. $X$ eats pizza every $5$ days, $y$ every $7$ days, and $z$ every $11$ days. $X$ & $Z$ had pizza together yesterday and $Y$ ...
-1
votes
2answers
55 views

Verify that 4(29!)+5! is divisible by 31. [duplicate]

Verify that 4(29!)+5! is divisible by 31. How do I work this out? Step by step explanation please!
0
votes
3answers
26 views

Prove if $\gcd(a,m)=1$ then $\gcd(a \mod m,m)=1$.

Prove if $\gcd(a,m)=1$ then $\gcd(a \mod m,m)=1$. Is there some simple elegant way of proving the above statement? I prove it by noting $div(a,m)=div(a\mod m,m)$, but it is a bit lengthy.
4
votes
0answers
85 views

Application of Dirichlet Theorem in AP to elementary number theory problems.

I have learnt this theorem in my class, however, "elementary" examples are very limited. (focusing more on analytic machinery) Are there any interesting applications to elementary number theory that ...
2
votes
0answers
77 views

How to prove sum of two numbers of the two following forms can be equals to sum of two numbers not of the forms?

The two forms are: $\ 3x^2 + (6y-3)x - y\ $ $\ 3x^2 + (6y-3)x + y - 1, \ \ x,y \in \mathbb{Z}^{+}$ For example: $\ \ \ 5 = \ 3*1^2 + (6*1-3)*1 - 1\ $ ,when $\ x = y = 1\ $,of the two forms $\ ...
1
vote
1answer
34 views

Divisor function of factorials and other integers

Is there a proof or any known value of $x$, for which $x<n!$ and $\sigma(n!)<\sigma(x)$
1
vote
2answers
38 views

Proving any $x \in [0,1]$ belongs to infinitely many $S^{k}_{n}:=[\frac{k-1}{2^n},\frac{k}{2^n}]$

I am trying to prove the following: Define $S^{k}_{n}:=[\frac{k-1}{2^n},\frac{k}{2^n}]$ i) Given any $x \in [0,1]$, then $x$ belongs to infinitely many $S^{k}_{n}$ ii) Any $x \in ...
0
votes
2answers
85 views

Find all solutions in positive integers of the Diophantine equation (proof explanation)

An example problem in my textbook asks: Find all solutions in positive integers of the diophantine equation $x^2 + 2y^2 = z^2$. The provided proof appears as follows: $2y^2 = z^2 - x^2 = (z - ...
1
vote
2answers
72 views

Chinese Remainder Theorem - Ground Plan of Existence Proof

Let $n_{1},\ n_{2},\ n_{3},\ \cdots,\ n_{r}$ be positive integers such that $\gcd(n_{i}, n_{j})=1$ for $1 \le \quad i\neq j \quad \le r$ Then the simultaneous linear congruences $ x\equiv a_i \pmod ...
0
votes
1answer
30 views

Do powers of 2 routinely neighbor powers of 3?

Let me write the question more precisely first: Is it true that for every $n\in\Bbb N$ there exists an $m\geq n$ and a $k\in\Bbb N$ such that $2^m = 3^k\pm 1$. I have tried various modular arithmetic ...
1
vote
1answer
52 views
1
vote
1answer
110 views

Bound of a certain sum of cosines

Let $N$ be a sufficiently large natural number and let $k \in \mathbb{N}$ such that $k | N$. Suppose I have a sequence $\{ \alpha_j \}_{j=1}^N \subseteq [0,1)$, which satisfies $$ \# \{ j \in \{1, ...
1
vote
2answers
951 views

gcd(a,b)=d then show that gcd(a/d,b/d)=1 (without euclids lemma or bezout's theorem)

I was solving the problem $\gcd(a,b)=d$ then show that $\gcd(\frac{a}{d},\frac{b}{d})=1$ (without Euclid's lemma or Bézout's theorem) then stumbled upon the fact that if we say ...
2
votes
1answer
57 views

Confusing sum of fractions

Question is to find the sum of: $$(\frac{1}{2^2-1})+(\frac{1}{4^2-1})+(\frac{1}{6^2-1})+(\frac{1}{20^2-1})$$ I know that $a^2-b^2=(a+b)(a-b)$, and that with this I can find the LCM to be 1995, ...
1
vote
1answer
57 views

Counting Argument

I'm trying to get the number of ways of doing something. I'm obviously doing it wrong because I'm not getting a whole number as the final answer. The question: How many pairs of numbers have ...
1
vote
2answers
67 views

If $30$ divides $p_1^4 + p_2^4 + \ldots + p_{31}^4$. Prove that $p_1=2$, $p_2=3$ and $p_3=5$.

Let $p_1<p_2<\cdots<p_{31}$ be prime numbers such that $30$ divides $p_1^4 + p_2^4 + \cdots + p_{31}^4$. Prove that $p_1=2$, $p_2=3$ and $p_3=5$. No clue how to start..Hints are welcomed.
0
votes
1answer
36 views

Proving that operations give equal results given equal inputs

I was reading about the 9 or 12 basic properties of 'fields' (if that's what they're called) in a book called Spivak's Calculus, 3rd Edition, and got quite befuddled by dealing with as basic stuff as ...
0
votes
1answer
97 views

Pythagorean quadruple generators with a gcd relation

For non-negative integers $m,n,q,p$ with $\gcd(m,n,q,p)=1$, assume we have: $$\gcd(mq+np,b)=|nq-mp|$$ for some integer $$b<mq+np$$ and that $$8\nmid\,mq+np,$$ $$m+n+p+q\equiv 1\mod 2.$$ Can ...
1
vote
2answers
116 views

Does the equation $x^n\equiv 1\pmod p$ has at most $n$ solutions?

Does the equation $x^n\equiv 1\pmod p$, $p$ being a prime has at most $n$ solutions? If it does, how to show it? (I don't know a thing about fields.)
4
votes
2answers
94 views

How do you refer to this Term in English?

How do you refer to this theorem in English exactly? $$a\mathbb Z+ b\mathbb Z =d\mathbb Z \text{, where }d = \gcd(a,b) \text{ and a, b}\in \mathbb Z$$ I imagine it should be something like: "The set ...
0
votes
1answer
72 views

Let $x, y, z$ be a primitive pythagorean triple. Show that exactly two of $x^2, y^2, z^2$ are congruent mod 7

So, I know that if x,y, and z are a pythagorean triple, then $x = m^2-n^2$, $y = 2mn$, $z = m^2+n^2$ How can I show that exactly two of $x^2, y^2, z^2$ are congruent mod 7?
1
vote
1answer
57 views

Primitive roots used to work out $x^7 \equiv 5 \pmod {11}$

I have a workbook question that doesn't have any example solution, that is as follows: Primitive roots used to work out $x^7 \equiv 5 \pmod {11}$ Now I can see $\phi(11)=10$ and $2$ has order $10$ ...
1
vote
3answers
78 views

Diophantine equations problem/exercise 3

Find all the pythagorean tripples (x,y,z) with x=40. Well I started with the known formulas for the pythagorean tripples but got me nowhere. Or I was not able continue the thought process required. I ...
2
votes
1answer
55 views

Diophantine Equations problem 2

Find all the solutions to the Diophantine equation x^2+y^2=2(z^2) .I do not have alot of expirience on Diophantine equations and i do not know how to approximate them.I can see that the tripples of ...
0
votes
1answer
132 views

Diophantine equation exercise [duplicate]

Prove that the diophantine equation $x^4-2(y^2)=1$ has only 2 solutions. Any hint on how to start and what to do .. I do not have a lot of experience on non linear diophantine equations and do not ...
3
votes
2answers
45 views

A square number and a positive cubic number which differ by six

Is there a square number and a positive cubic number (both positive integers) which differ by six? If not, how do we prove this?
0
votes
1answer
58 views

What is the largest integer m satisfying a^12 = 1 (mod m) for all integers a relatively prime to m

What is the largest integer m satisfying $a$$^{12}$ = 1 (mod $m$) for all integers a relatively prime to m? I believe this can be solved using a homomorphism. So, let $m$ = ...
1
vote
2answers
51 views

Proving congruence modulo .

Can you guide me through this proof. Prove n2≡(7−n)2(mod 7). where n is an integeer
3
votes
1answer
81 views

What suggests the first step in this proof of Fermat's Little Theorem?

I've recently started looking at various different proofs of Fermat's Little Theorem, which states that, for $p$ a prime and $a$ an integer not divisible by $p$, that $a^{p-1} \equiv 1 \mod{p}$. ...
2
votes
1answer
73 views

Find all integers n such that n−2014 and n+ 2014 are both triangular numbers.

I came across this problem when searching for triangular numbers questions. I know that I need to use the equation, $$\frac {n(n+1)}{2} $$ but I don't know how to apply it to this problem.
0
votes
2answers
81 views

GCD and LCM Problem

Let $x$ and $y$ be positive integers, $x < y$, and $x + y = 667$. Find all pairs $(x,y)$ if $\text{lcm}\,(x,y)/\gcd\,(x,y) = 120$. This problem was from my number theory homework, and I don't get ...
2
votes
1answer
183 views

Solve for x when $2222^{5555} + 5555^{2222} \equiv x \pmod{7}$ [duplicate]

I need to find the remainder when $2222^{5555} + 5555^{2222}$ is divided by $7$. I'm thinking that Fermat's Little Theorem might help. Any suggestions?
4
votes
2answers
158 views

Finding rational points on a non-trivial algebraic curve

The curve in question is defined as the set of all points $(x,y)$ where both $x$ and $y$ are in $(0,1)$, and that satisfy the following: $$ \left( x^4 - 6 x^2 + 1 \right) \left( y^4-6y^2+1 \right) ...
1
vote
1answer
96 views

Why must a primitive root be less than and relatively prime to n?

"For instance there are no primitive roots modulo 8. To see this note that the only integers less than 8 and relatively prime to 8 are 1, 3, 5, and 7..." The author then proceeds to show that the ...
1
vote
1answer
50 views

Finding solution of this equation in set of positive integers.

Could you help me to obtain solutions of the equation $2^{2k+1}-n^2 =1$ in set of positive integers, where $k$ and $n$ are positive integers. In case there is no solution, how to prove it. Thanks in ...
2
votes
2answers
562 views

Show that an integer of the form $8k + 7$ cannot be written as the sum of three squares.

I have figured out a (long, and tedious) way to do it. But I was wondering if there is some sort of direct correlation or another path that I completely missed. My attempt at the program was as ...
0
votes
1answer
64 views

Pythagorean Triple parametrization

For the pythagorean tripple (x,y,z) such that $x^{2} + y^{2} = z^{2}$ , we know that $x,y,z$ can't be all odd, which means either x,y or z must be even. We can choose y even to get many ...
0
votes
1answer
33 views

Determine the set of odd primes for which a quadratic residue modulo $p$, $p$ 'large'

though this one may seem a duplicate of - say - this: Determine all primes p for which 5 is a quadratic residue modulo p, well, I have a question. How would you manage the problem of determining the ...