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

learn more… | top users | synonyms (1)

0
votes
0answers
3 views

Finding a point using complex geometry

In the Cartesian plane let $A = (1,0)$ and $B = \left( 2, 2\sqrt{3} \right)$. Equilateral triangle $ABC$ is constructed so that $C$ lies in the first quadrant. Let $P=(x,y)$ be the center of ...
1
vote
1answer
56 views

Number of zeros at the end of $k!$

For how many positive integer $k$ does the ordinary decimal representation of the integer $k\text { ! }$ end in exactly $99$ zeros ? By inspection I found that $400\text{ !}$ end in exactly $99$ ...
4
votes
1answer
40 views

$\lfloor x^k \rfloor \equiv m \pmod{n}$ with $x$ irrational

Let $x>1$ be an irrational number, and $n$ a positive integer. Is it true that, for each integer $m$, there exists an integer $k$ such that $$ \lfloor x^k \rfloor \equiv m \pmod{n}? $$
-1
votes
0answers
15 views

How can I use diophantine approximation to find a real number?

I have been told that the following question can be solved using Diophantine approximation, but I cannot find a way to solve it. I have no prior knowledge of Diophantine approximation and so I ...
13
votes
1answer
720 views

Two numbers that cannot both be squares

I was wondering where to start with the following question: Show for $a,b \in \mathbb{N}$ that $a+b^2$ and $a^2+b$ cannot be both squares. Here $\mathbb{N}$ is the positive integers ($0$ not ...
0
votes
1answer
23 views

What is the size of Range?

Suppose d=gcd$(a,n)$ where $a, n \in \mathbb{Z}, n>0$ and $f_a: \mathbb{Z_n} \to \mathbb{Z_n} \\ \qquad x \to ax\texttt{ mod } n$ The size of Domain is evident and for the size of Range my ...
0
votes
3answers
35 views

Divisibility puzzle

A number, when divided by 2, 3, 4, 5, or 6, leaves 1 as remainder, while the same number leaves no remainder when divided by 7. What is the least number with these properties? The answer is 301. How ...
5
votes
1answer
185 views

Wilson's Theorem - Why only for primes? [on hold]

Why is it true that Wilson's Theorem only holds for prime numbers? I read a proof of it, and it did not seem to cater to that aspect of the theorem.
10
votes
4answers
3k views

Can you complete the expression 2 _ _ _ _ 5 = 2015?

Can you complete the expression 2 _ _ _ _ 5 = 2015 and make it correct by replacing two underscores with a selection of the operational symbols $+, - , ...
0
votes
2answers
24 views

Inequality involving floor

Let $x$ be randomly chosen from $\{1,...n\}$. Define $X_{p}$ such that \begin{equation} X_p= \begin{cases} 1, & \text{if}\ p|x, \\ 0, & \text{otherwise.} ...
0
votes
0answers
19 views

Is $\sum\limits_{{\rm{i}} = 1}^{n - k} {{b_i}} \times {b_{n-2}} + b_{k}$ correct to express this pattern in base n?

having seen the pattern be,ow i have tried to express it in base n, of course there should be few constraints added to parameters. $$\begin{align} 1 \times 8 + 1 &= 9\\ 12 \times 8 + 2 &= ...
1
vote
0answers
20 views

Simple clarification- big $O$ and small $O$ notations in Erdos-Kac theorem proof

From The Probabilistic Method by Alon and Spencer. Let $\nu(n)$ be the number of primes $p$ dividing $n$ and set \begin{equation} X_p= \begin{cases} 1, & \text{if}\ p|x, \\ ...
0
votes
6answers
222 views

Alternate ways to prove that $4$ divides $5^n-1$

I was working for various method to solve this: For all $n\in \mathbb N$: $4\;\mid\;(5^{n}-1)$. My try was: 1st: $$n=1 \to 4|5^1-1\\n \geq 2 \to 5^n=25,125,625,3125,...\\ n\geq 2 \to ...
1
vote
2answers
47 views

Seating people in a circular table

It has always been an interesting question. If we have $10$ chairs and a round table, how many ways are there of seating $10$ people? I would say there are $10!$ ways to seat the people due to ...
5
votes
3answers
76 views

How to prove there are no solutions to $a^2 - 223 b^2 = -3$.

As the title suggests, I'm trying to prove that there are no solutions to $a^2 - 223b^2 = -3$ (with $a,b\in \mathbb{Z}$). Ordinarily, taking both sides $\mod n$ for some clever choice of $n$ proves ...
-1
votes
2answers
30 views

Does the order in a circular arrangement matter?

I posted a question a while ago: Ten chairs are arranged in a circle. Find the number of subsets of this set of chairs that contain at least three adjacent chairs. My question here is: imagine a ...
4
votes
1answer
61 views

Solution to Diophantine equation $\frac{1}{x^2}+\frac{1}{y^2}=\frac{1}{z^2} $

I have to prove the following, but I don't know how to start. The only solutions in positive integers of the equation $$ \frac{1}{x^2}+\frac{1}{y^2}=\frac{1}{z^2} \qquad \gcd(x,y,z)=1 $$ ...
19
votes
4answers
1k views

Visualizing the factorial

Often in basic mathematics, we can visualize things very easily, which I believe helps understanding (instead of just working out a number theoretical proof). For example: $$(n+1)^2 - n^2 = (n+1) +n$$ ...
0
votes
1answer
31 views

How many pairs of $(x, y)$ satisfied this equation

I need help to solve in $\mathbb{Z}$ the following equation $$yx^{2}+xy^{2}=30$$ I tried to solve it by factor $30$ to $5\times 6$ and I get those two pairs $(2, 3) \& (3, 2) $... is their any ...
2
votes
2answers
377 views

Stars and Bars vs PIE

I randomly made up this question so I could check: There are $3$ kids and $6$ gifts, how many ways to distribute so that each kid has at least one gift. Obviously, $**|**|**$ there are ...
-4
votes
0answers
20 views

Condensation of a number [on hold]

a)Let the first 2004 natural numbers be written 'at a stretch' to form a new number N.In other words, consider the number $$N = 12345678\ldots 200220032004$$ Find the number of digits of N.Let the ...
0
votes
0answers
31 views

Find number of element in $\{m\in\mathbb N:m\leq n\text{ and }m\text{ has the digit 3}\}$.

Inspired by a youtube video claiming that "almost all positive integer has the digit 3", I set myself a challenge: Give a formula, in terms of $n$, for the number of positive integer that is less ...
-2
votes
3answers
64 views

Division problems

I came across these problems : 1) Find the lowest natural number $k$ that satisfies the condition : $ 7 \mid A$ , where $A = 194^{19} + 125^{14} + k $ 2) Find the different prime numbers ...
5
votes
3answers
412 views

Problem Solving Positive Integers

This is a very interesting word problem that I came across in an old textbook of mine. So I know the maximum value of the HCF has to be a factor of $540$ and mayhaps the Euclidean Algorithm, but other ...
4
votes
1answer
55 views

How to prove that any natural number $n \geq 34$ can be written as the sum of distinct triangular numbers?

Sloane's A053614 implies that $2, 5, 8, 12, 23$, and $33$ are the only natural numbers $n \geq 1$ which cannot be written as the sum of distinct triangular numbers (i.e., numbers of the form ...
5
votes
2answers
156 views

Prove that every integer $n\geq 7$ can be expressed as a sum of distinct primes.

My teacher said to use Bertrand's postulate and I have tried this for so long and I seem to go nowhere. Help would be appreciated. EDIT: Here's what I've done in my proof so far (I need help ...
3
votes
2answers
94 views

at least one of 100 consecutive integers is relatively prime to all natural numbers less or equal 100

For an arbitrary integer $n$ define $A_n=\{i|n \leq i \leq n+99 \text{ where }i\text{ is an integer}\}$ (i.e. $A_n$ is 100 consecutive integers) Is it true that for any integer $n$ there is an ...
2
votes
3answers
69 views

Why would the cubic have $5$ roots?

The polynomial $P(x)$ is cubic. What is the largest value of $k$ for which the polynomials $Q_{1}(x) = x^{2}+(k-29)x-k$ and $Q_{2}(x) = 2x^{2}+(2k-43)x+k$ are both factors of $P(x)$? $P(x) = ...
3
votes
2answers
45 views

Find the least $N$ so there is no square

Find the least positive integer $N$ such that the set of $1000$ consecutive integers beginning with $1000 \cdot N$ contains no square of an integer. Let $x^2$ appear before $1000N$ so: $(x+1)^2 ...
-1
votes
0answers
64 views

How does constructing numbers in a set theoretic way help mathematics?

I recently read that the natural numbers can be constructed within the framework of the Zermelo-Fraenkel axioms via de axiom of infinity, where, with $n$ a natural number $n+1=n\bigcup \{n\}$ and ...
0
votes
2answers
55 views

How many divisors of the combination of numbers?

Find the number of positive integers that are divisors of at least one of $A=10^{10}, B=15^7, C=18^{11}$ Instead of the PIE formula, I would like to use intuition. $10^{10}$ has $121$ divisors, ...
1
vote
1answer
37 views

How to use Principle of Inclusion-Exclusion here?

A while ago I posted a question: Coloring a Grid. Online, I seem to have stumbled upon a usage of PIE AOPS Wiki Solution AIME II #9. (1) Now, I have experience with PIE, but I do not see how to ...
12
votes
2answers
457 views

Show divisibility by 7

I was stuck at this question: Suppose $a^2+b^2=c^2$ for $a,b,c \in \mathbb Z$, and neither $a$ nor $b$ is a multiple of 7. Show that $a^2-b^2$ is a multiple of 7 I tried to write $b^2$ as ...
1
vote
1answer
48 views

Probability of getting a five digit number divisible by 5 but with no two consecutive digits identical

A five digit number is written down at random. What is the probability of getting a number that is both divisible by 5 and doesn't have any 2 consecutive digits identical? I tried to analyse the ...
1
vote
2answers
129 views

How come $\ n\ $ always divides at least one of the item of the sequence?

Given positive integer$\ \displaystyle n,\ $ the sequence is: $\displaystyle 2^n$ $\displaystyle 2^n - 2^{n-1}$ $\displaystyle 2^n - 2^{n-1} + 2^{n-2}$ $\displaystyle 2^n - 2^{n-1} + 2^{n-2} - ...
1
vote
2answers
39 views

To calculate the remainder of (111…) + (222…) + (333…) + (444…) + (555…) + (666…) +(777…) by 37

To Evaluate the remainder Question: $ (111...) + (222...) + (333...) + (444...) + (555...) + (666...) +(777...)$ mod $37$ In each bracket, the single digit $(1, 2, 3, ..., 7)$ is written $110$ ...
-2
votes
1answer
35 views

How would one solve the following equation: $(n-1)! +1 = nm$ [on hold]

Assume we do not know the Wilson's theorem, how would one solve this equation: $(n-1)! +1 = nm$ to show that there are infinite ...
-2
votes
2answers
93 views

Solve $x,y\in \mathbb{Z}$ [on hold]

Solve for $x,y\in \mathbb{Z}$ $$x^{6}=y^{2}+53$$ I tried but I couldn't complete
0
votes
2answers
39 views

Can we obtain the pair $(1,50)$ with these following operations?

It's a problem from some russian competition: We're given a card with two positive integers $(a,b)$ and we have tree machines which generate another card from the one we insert on it(I assume we ...
1
vote
0answers
21 views

Proof of x = 0 modulo 3 only if the sum of its digits 0 modulo 3 [duplicate]

Okey, lets beggin from a helpfull proposition I've already proved: $$$$ if $a_i\equiv b_i\:\forall 0\le i\le m$ then to any $m$ numbers: $p_1,p_2,...,p_m\in \mathbb{Z}$ $$\sum ...
1
vote
2answers
70 views

Ways of coloring the $7\times1$ grid (with three colors)

Hints only please! A $7 \times 1$ board is completely covered by $m \times 1$ tiles without overlap; each tile may cover any number of consecutive squares, and each tile lies completely on the ...
2
votes
2answers
30 views

Binary expansion, finding the greatest power of $2$ less than a given number

I'm looking to better understand binary for a CS50 problem set. I'm not understanding transferring decimal notation to binary. For example, use 237. How to find the largest power of $2$ less than ...
2
votes
2answers
55 views

What is the remainder when 50^51^52 divided by 11?

To find the remainder: $$50^{51^{52}} \mod 11$$ I have solved till: $$6^{51^{52}} \mod 11$$ But not able to proceed further. Help please.
4
votes
4answers
102 views

Greatest of the numbers given [duplicate]

To find out the greatest among the number given below: $3^{1/3}, 2^{1/2}, 6^{1/6}, 1, 7^{1/7}$ I have plotted the following graph using graph plotter which is shown below: It can be concluded that ...
3
votes
3answers
128 views

prove that $\dfrac{\left( 5^{125}-1\right)}{\left( 5^{25}-1\right)}$ is composite number

Prove that $\dfrac {\left( 5^{125}-1\right)}{\left( 5^{25}-1\right)}$ is composite number using number theory. Do not use calculator or Wolfram alpha or anything like that.
46
votes
3answers
761 views

Finding triplets $(a,b,c)$ such that $\sqrt{abc}\in\mathbb N$ divides $(a-1)(b-1)(c-1)$

When I was playing with numbers, I found that there are many triplets of three positive integers $(a,b,c)$ such that $\color{red}{2\le} a\le b\le c$ $\sqrt{abc}\in\mathbb N$ $\sqrt{abc}$ divides ...
3
votes
1answer
59 views

How can I find the answer to $\varphi(2^{400} + 2)$?

How can I find the answer to $\varphi(2^{400} + 2)$ ? So far I have $\varphi(2^{400}) = 2^{400} - 2^{399} = 2^{399}(2 - 1) = 2^{399}$ I'm guessing the answer will be in the form of an exponent like ...
2
votes
1answer
540 views

Find an inverse of $a$ modulo $m$ for each of these pairs of relatively prime integers

How would I find the inverse of a given number $a$ modulo $m$, given that $\gcd(a,m)=1$? a) $a = 2$, $m = 17$ $17 = 2 \cdot 8 + 1$ $2 = 1 \cdot 2 + 0$ $1 = 17 - 8 \cdot 2$ <-How do I know ...
114
votes
9answers
5k views

What does $2^x$ really mean when $x$ is not an integer?

We all know that $2^5$ means $2\times 2\times 2\times 2\times 2 = 32$, but what does $2^\pi$ mean? How is it possible to calculate that without using a calculator? I am really curious about this, so ...
13
votes
3answers
949 views

Numbers are too large to show $65^{64}+64^{65}$ is not a prime

I tried to find cycles of powers, but they are too big. Also $65^{n} \equiv 1(\text{mod}64)$, so I dont know how to use that.